[RL] 벨만 방정식

Bellman Equation(벨만 방정식)이란?

반환값과 상태가치함수 리뷰

반환값
- 타입스텝 t에서 계산한 누적 보상의 합계
- 에피소드 하나에 대한 가치를 측정

상태 가치 함수
- 환경 전체에 대한 가치를 측정
- 상태 전이 확률을 같이 고려함

MRP 벨만 방정식

강화학습에서 프로그래밍으로 가치를 구하기 위해 '벨만 방정식'을 많이 사용
수학자 리처드 어니스트 벨만의 이름을 땄음

일반적으로 기댓값을 시그마 기호를 사용한 수열의 합으로 표현
현재 상태의 가치함수와 다음 상태의 가치함수 관계로 나타냄

수식 1 = 개념적인 상태 가치 함수
수식 2 = 상수는 기댓값에서 의미 X, 정리함
수식 3 = 기댓값을 수열의 합과 다음 상태에서의 상태 가치 함수로 나타낸 것

MDP 벨만 기대 방정식

0단계

벨만 기대 방정식
: 현재 상태의 가치 함수와 다음 상태의 가치함수의 관계를 식으로 나타냄

상태 가치함수(반환값의 기댓값)에서 유도되었음
= 한 스텝만큼 진행해서 보상을 받고,
그 다음 상태(St+1)부터 미래에 받을 보상을 더해줌

위 수식은 Gt를 풀어서 작성하고,
감마로 묶어 현재 상태의 가치함수 + 다음 상태의 가치함수로 표현

행동 가치함수도 위와 같이 표현 가능

1단계

상태 가치 함수를 0단계와 달리 정의할 수 있음
다음과 같이 정의할 수 있는 이유는 행동가치함수 역시 리턴의 기댓값
즉, a를 실행할 확률을 안다면 상태 가치함수로 나타낼 수 있다.

s 상태의 가치함수
: a1 행동을 취한 후 받는 반환값과 a2 행동을 취한 후 받는 반환값 모두 고려

위 경우 상태 s에서의 행동 가치함수는 2가지.
하나의 액션 밸류(q)는 행동 a1에 대한 반환값들에 대해서 기댓값
또 다른 액션 밸류(q)는 행동 a2에 대한 반환값들에 대해서 기댓값

각 행동을 했을 때의 액션 밸류에 그 행동이 일어날 확률을 곱해서
모든 행동에 대해 그 값을 더해주면 상태 가치함수가 된다.

정책 𝜋가 두 액션을 선택할 확률은 각각 60%, 40%
또한 액션 밸류는 각각 1, 2이다.

정책과 각각의 액션 밸류를 알고 있으므로 위와 같이 계산 가능

또한, 상태의 밸류를 안다면 액션 밸류 함수로 정의 가능

예제로 연습

0단계는 전이 확률(P)를 알고 있고,
행동 a를 선택한다고 가정했기에 확률 변수가 제거되어 기댓값을 없앴음
전이 확률이 1이 아니라면 행동에서 다음 상태로 뻗는게 여러 개일 수 있다.

MDP 성질로 인해 무조건 정해진 다음 상태가 나타나는
결정적인 환경이 아니라면, 외부 요인에 다른 상태로 갈 수 있기 때문

즉, 원래의 보상함수는 상태에 대한 보상함수이지만,
행동을 정했기 때문에 그 행동에 대해 즉시 얻는 보상으로 대체 가능

따라서 행동 가치 함수는 특정 행동을 한 뒤
즉시 받는 보상에 행동을 통해 각 다음 상태로 갈 확률 * 다음 상태 밸류를 더한 것(감가율 적용)으로 표현함

2단계

위에서 정의한 상태가치함수와 행동가치함수에 대입

0단계와 2단계 비교

0단계 식
: 현재 상태의 가치와 다음 상태의 가치를 기대값 연산자를 통해 연결

2단계 식
: 마찬가지로 현재 상태의 가치와 다음 상태의 가치 사이의 연결고리,
0단계에 있는 기댓값 연산자를 모두 확률과 가치의 곱 형태로 풀어 씀

2단계 수식을 위한 2가지 개념

MDP를 안다 == 보상함수와 전이확률을 알 때
MDP를 모른다 == 보상함수와 전이확률을 모를 때

보상함수와 전이확률은 환경의 일부이므로 위 2가지가 중요
실제 문제의 상황에서는 이에 대한 정보를 모를 때가 더 많다.
즉, 모르는 상황에서도 강화학습을 해야한다.

MDP를 안다

보상함수 + 전이확률 O

• Model-Based 혹은 Planning 접근법
  → 실제로 경험하지 않고 머리속에서 시뮬레이션으로도 적용 가능
• 2단계 벨만 기대 방정식 사용

MDP를 모른다

보상함수 + 전이확률 X

• Model-Free 접근
  → 그 상태에서 실제 액션을 해보고 경험을 통해 학습함
• 0단계 벨만 기대 방정식 사용

MDP 벨만 최적 방정식

최적 방정식 개요 (벨만 기대 방정식과의 차이)

벨만 기대 방정식은 모두 정칙이 𝜋로 고정일 때 가치에 관한 함수
그러나, 벨만 최적 방정식은 최적 밸류에 대한 함수

어떤 MDP가 주어졌을 때,
해당 MDP 안에 존재하는 모든 𝜋중에서 가장 좋은 𝜋를 선택하여 계산 = 최적 밸류
가장 좋은 𝜋로 계산했기 때문에 가장 높은 밸류를 갖는다.

만약 s1 ~ s5 상태에서는 𝜋1이 더 높고,
s6 ~ s10 상태에서는 𝜋2가 더 높다면 ?
-> 두 정책 중 어느 정책이 더 높다고 하기 어려움

MDP 내에 모든 𝜋중 반드시 우수한 𝜋가 있기 때문에
어느 MDP라도 최적의 정책이 존재함

최적의 정책(𝜋)만 정의되면 다음 등식을 따름

밸만 기대 방정식에서 정책 𝜋가
- 액션을 선택할 때의 확률적 요소
- 전이 확률에 의해 다음 상태를 선택할 때의 확률적 요소
총 2가지의 확률 변수가 있었음

하지만, 밸만 최적 방정식에서는 𝜋에 의한 확률적 요소가 사라짐
액션을 확률적으로 선택하는게 아니라, 제일 좋은 액션을 선택.

0단계

• 밸만 기대 방정식 0단계

최적의 정책을 선택할 것이기에 최댓값 연산자를 사용
전이 확률이라는 확률 변수가 아직 있기에 여전히 기댓값 필요함

1단계

• 밸만 기대 방정식 1단계

상태 s의 최적 밸류는
s에서 선택할 수 있는 액션 중 가장 높은 액션 밸류와 동일

밸만 기대 방정식 1단계에서는
𝜋(a|s)라는 액션을 선택할 확률이 곱해졌는데
밸만 최적 방정식은 100% 확률로 최적 액션을 선택하므로
액션 함수는 위와같이 정의됨

2단계

1단계의 수식을 서로 조합하여 대입함

최적 상태가치 함수에는 최적 액션함수를
최적 액션함수에는 최적 상태가치 함수를