[오승상 강화학습] 04. Reward and Policy

1. Reward

Reward $R_t$ 는 $t$ 단계(present time step)에서 agent의 수행 정도를 평가하는 scalar feedback이다.
Agent의 임무는 total reward를 maximize 하는 방향으로 학습하는 것이다.
또한, RL은 **Reward Hypothesis**에 기반을 두고 있다.

1-1. Reward Hypothesis

RL에서 모든 목표는 임의의 stochastic policy에서 나타날 수 있는 각각의 episode에 대한 total reward(cumulative sum of reward)들의 기대값(expected value)을 maximize 하는 방향으로 agent를 학습해야 한다.
이것이 RL의 가장 기본적인 방향이 된다.

1-2. Reward function

일반적으로 다양한 유형의 reward function이 사용된다.
e.g. 바둑(Go game) : 한 게임(episode)가 끝나면 승자에게 보상이 주어짐

| $R_{s} = R(s)$ | 현재 state에 대한 reward | | $R^{a}_{s} = R(s, \ a)$ | 현재 state $S_t=s$ 에서 어떤 action $A_t=a$ 를 취했을 때 얻는 reward | | $R^{a}_{ss^{\prime}} = R(s, \ a, \ s^{\prime})$ | 현재 state $S_t = s$ 에서 어떤 action $A_t=a$ 를 취해서 $S_{t+1}=s^{\prime}$ 로 전이될 때 얻는 reward |

2. Expected Reward

2-1. Dynamics

Agent가 environment와 상호작용할 때, 특정 state에서 특정 action을 취했을 때 환경이 어떻게 변화할지를 결정하는 물리적 법칙이나 규칙을 의미한다.
Dynamics는 수학적으로 transition probability나 transition function으로 정의된다.

MDP model example 1

$p(s^{\prime} \mid s, \ a) = 0.4$

현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을때, 다음 state가 $S_{t+1}=s^{\prime}$ 일 확률

$p(s^{\prime}, \ r^{\prime} \mid s, \ a) = 0.4$

현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을때, 다음 state가 $S_{t+1}=s^{\prime}$ 이고, reward $r^{\prime}$ 을 받을 확률

MDP model example 2 (Dynamic programming)

$p(s^{\prime} \mid s, \ a) = 0.4$

현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을때, 다음 state가 $S_{t+1}=s^{\prime}$ 일 확률

$p(s^{\prime}, \ r^{\prime} \mid s, \ a) = 0.2$

현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을때, 다음 state가 $S_{t+1}=s^{\prime}$ 이고, reward $r^{\prime}$ 을 받을 확률

$p(s^{\prime}, \ r^{\prime \prime} \mid s, \ a) = 0.2$

현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을때, 다음 state가 $S_{t+1}=s^{\prime}$ 이고, reward $r^{\prime \prime}$ 을 받을 확률

2-2. State transition probability

2-3. Expected reward for state-action pair

2-4. Expected reward for state-action-next state triple

3. Return

3-1. Return

G_t = \gamma^{0}R_{t+1} + \gamma^{1}R_{t+2} + \gamma^{2}R_{t+3} + \cdots = \sum_{k=0}^{\infty} \ \gamma^{k}R_{t+k+1}

Return $G_t$ 는 현재 time step $t$ 이후에 받게 될 total discounted reward 이다.

3-2. Discount factor

할인율 또는 감가율 이라고 불리며, 0 ~ 1 사이의 값을 갖는다. ( $\gamma \in [0, \ 1]$ )
$\gamma$ 가 0에 가까우면, 미래 reward에 곱해지는 $\gamma^{k}$ 가 빠르게 0이 되므로, 당장 받는 보상(immediate rewards)에만 신경 쓰게된다. (myopic, 근시안적)
$\gamma$ 가 1에 가까우면, 미래 reward도 거의 깎이지 않고 그대로 반영되므로, 먼 미래에 받게될 보상(future rewards)도 고려한다. (far-sight, 멀리 내다봄)

3-3. MDP에서 discount factor를 사용하는 이유

수학적 편리함

continuing task에서 $\gamma < 1$ 이면 expected total reward가 발산하지 않고 유한하게 수렴한다.

미래의 불확실성

일반적으로는 stochastic policy를 사용하므로, 먼 미래일수록 불확실성을 가진다. 그래서 그만큼 discount factor를 지수적으로 낮춘다.

즉각 보상 선호

현실에서도 즉각적인 보상(immediate reward)이 지연된 보상(delayed reward)보다 선호되는 경향을 반영한다.

유한 종료 시 생략 가능

모든 episode가 finite time에 끝난다면, discount factor를 사용하지 않기도 한다.

4. Policy

4-1. Deterministic policy

\pi(s) = a

결정적 정책은 주어진 state에 대해 하나의 action을 확정적으로 대응시킨다.
위 이미지 에서는 return이 가장 큰 action인 $a_2$ $a_{2}$ 를 확정으로 선택하였다.
- $\pi(s)=a_2$

4-2. Stochastic policy

\pi(a \mid s) = P(A_t=a \mid S_t=s)

확률적 정책은 주어진 state에 대한 action들의 확률 분포(probability distribution)이다.
위 이미지 에서는 각 action에 대해 return을 참고하여 확률을 분포하였다.
- $\pi(a_1 \mid s) = 0.15$
- $\pi(a_2 \mid s) = 0.8$
- $\pi(a_3 \mid s) = 0.05$

4-3. Policy의 역할

P(S_{t+1}=s^{\prime} \mid S_t=s)= P(S_{t+1}=s^{\prime} \mid S_0=s_0, \ S_1=s_1, \ \dots \ ,S_t=s)

Return(= total discount reward) 값을 maximize 하는 것
이를 위해서는 각 state 마다 어떤 action을 취하는 것이 좋은지(optimal action) 알려주는 가이드 라인
단, Markov property에 의해 다음 state로의 transition probability는 오직 현재 state에만 의존하고, 그 이전의 과거 state와는 무관하다.

4-4. Known MDP (Model-based)

transition probability를 알고 있기 때문에 expected reward에 대한 계산이 가능하다.
따라서, known MDP의 경우에는 deterministic optimal policy $\pi_*(s)$ 를 찾을 수 있다.
e.g. Dynamic programming → known MDP를 이용해서 deterministic optimal policy를 찾는 문제

4-5. Unkown MDP (Model-free)

경험(sample data)과 같은 한정적인 정보만 알고 있다.
transition probability를 모르기 때문에 ** $\epsilon - greedy$ policy(stochastic policy)**를 사용한다.
e.g. Reinforcement Learning

4-6. $\epsilon - greedy$ policy (stochastic policy)

미래를 생각하지 않고 각 단계에서 가장 최선의 선택을 하는 기법
즉, 각 단계에서 최선의 선택을 한 것이 전체적으로 최선이길 바라는 알고리즘
추후 RL 에서 다시 보도록 한다.
$\epsilon = 0.1$ , action 5개
위 예제 model에서 **초록색**은 알고 있는 샘플 데이터, **파란색**은 **모르는 데이터**라고 가정한다.
sample data를 이용해서 학습한 결과, $a_2$ 의 expected total reward가 가장 크므로 $a_2$ 를 best action으로 본다.

⇒ $1-\epsilon$ : choose the optimal value(greedy), $\epsilon$ : choose randomly

$\epsilon$ 값을 모든 action에 균등 배분

\frac{\epsilon}{n} = \frac{0.1}{5} = 0.02

Best action $a_2$ 의 action select probability

(1-\epsilon)+0.02 = (1-0.1) + 0.02 = 0.92

나머지 action들의 action select probability

a_1, \ a_3, \ a_4, \ a_5 = 0.02

5. Summary of notation

$P(X=x)$

$X$ 는 random variable(확률 변수)를 의미하고, $x$ 는 특정 값을 의미한다.
random variable $X$ 가 특정한 값 $x$ 를 가질 확률
간략하게 다음과 같이 표현하기도 한다. → $p(x)$

$\mathbb E [X]$

random variable $X$ 의 expectation(기댓값)
$i.e., \ \ \ \ \ \mathbb{E}[X]=\Sigma_{x} \ p(x)x$

$\max_{a} f(a)$

집합 $\{a\}$ 에서 $f(a)$ 의 최대값

$\operatorname*{arg\,max}_{a} f(a)$

$f(a)$ 가 최대값을 가질때의 $a$ 값 (argument of maximum)

$S_t, \ A_t, \ R_t$

시간 $t$ 에 대한 state, action, reward
이는 이전 state $S_{t-1}$ 에서 action $A_{t-1}$ 을 취했을 때 stochastically 얻어지는 값들이다.

$G_t$

return
시간 $t$ 이후에 얻어지는 reward들에 대한 total discounted reward

$p(s^{\prime} \mid s, \ a)$

state transition probability
현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을 때, 다음 state가 $S_{t+1}=s^{\prime}$ 이 될 확률

$p(s^{\prime}, \ r \mid s, \ a)$

reward까지 고려한 state transition probability
현재 state $S_t=s$ 에서 action $A_t=a$ 를 취했을 때, 다음 state가 $S_{t+1}=s^{\prime}$ 이 되면서 reward가 $R_{t+1}=r$ 이 될 확률

$\pi$

policy (decision-making rule)
모든 state에 대해서 어떻게 action을 취할 것인가를 정하는 정책

$\pi(a \mid s)$

stochastic policy
policy $\pi$ 가 주어져 있을때, state $s$ 에서 action $a$ 를 취할 확률

$\pi(s)$

deterministic policy
policy $\pi$ 가 주어져 있을때, state $s$ 에서 취하게될 action

5-1. State-Value function

Dynamic programming에서 주로 사용
State-Value function

$v_{\pi}(s)$

state-value function (상태-가치 함수)
policy $\pi$ 가 주어졌을 때, state $s$ 이후로 얻게되는 가치(목표)의 기댓값 (expected return)

$v_{*}(s)$

optimal state-value function (최적 상태-가치 함수)
optimal policy $\pi_{*}$ 가 주어졌을 때, state $s$ 이후로 얻게되는 가치(목표)의 기댓값 (expected return)

5-2. Action-Value function

Reinforcement Learning에서 주로 사용
Action-Value function

$q_{\pi}(s, \ a)$

action-value function (행동-가치 함수)
policy $\pi$ 가 주어졌을 때, state $s$ 에서 action $a$ 를 취한 이후로 얻게되는 가치(목표)의 기댓값 (expected return)

$q_{*}(s, \ a)$

optimal action-value function (최적 행동-가치 함수)
optimal policy $\pi_*$ 가 주어졌을 때, state $s$ 에서 action $a$ 를 취한 이후로 얻게되는 가치(목표)의 기댓값 (expected return)

References

고려대 오승상 강화학습 04 Reward and Policy