Control with Function Approximation

Action Value Function + Policy Improvement + Selecting Action

• state value function -> action value function
• policy improvement
• selecting action

GPI 의 패턴에 따라, 함수 추정을 사용하는 prediction ( policy evalution ) 방법을 control ( policy improvement ) 방법으로 확장할 것이다.

처음에는 state-value function 을 action value function 으로 확장할 것이며,

이를 policy improvement 와 행동 선택 기법들과 병합할 것이다.

그리고, 지금껏 그래왔듯이, on-policy 또는 off-poilcy 를 통해 다른 정책에 대한 '탐험'을 해결한다. (?)

Extension to Action Value Function

이전에는 상태에 대해 함수 추정을 적용 했지만,

$s_t \mapsto v_t$

이를 Action Value Function 으로 적용하면, 행동이 추가 된다.

$s_t, a_t \mapsto v_t$

여기서 함수 추정의 target output 인 $v_t$ 는

Monte Carlo return 인 $R_t$ 되거나 혹은 ,

one step Sarsa-style return 인 $r_{t+1} + \gamma Q_t ( s_{t+1} , a_{t+a} )$ 가 된다.

General Gradient Descent

Action Value Function 에 대한 Gradient Descent 갱신 방법은 아래와 같다.

$\vec Q_{t+1} = \vec Q_t + \alpha [ v_t - Q_t ( s_t , a_t ) ] \nabla _{ \vec \theta _t } Q_t ( s_t , a_t )$

Gradient Descent Sarsa ( $\lambda$ )

Action-value 방법에 대한 backward 관점에서의 $\theta$ 갱신 방법은 아래와 같다.

$\vec \theta _{t+1} = \vec \theta _t + \alpha \delta _t \vec e _t$

여기서 $\delta _t$ 는

$\delta _t = r _{t+1} + \gamma Q_t ( s _{t+1} , a _{t+1} ) - Q_t ( s_t , a_t )$

이며, $\vec e_t$ 는

$\vec e_t = \gamma \lambda \vec e _{t-1} + \nabla _{ \vec \theta _t } Q_t ( s_t , a_t )$

이며, 초기 벡터 e 는 0 벡터이다.

$\vec e _0 = \vec 0$

Policy Improvement & Action Selection

Control 방법을 만들기 위해서, action-value prediction 방법과 policy improvement 기법, 행동 선택 기법을 연동할 것이다.

Only for Small set Actions

행동의 집합이 크거나, 연속적인 행동에 적용 가능한 기법에 대한 알고리즘은 연구중이다.

개별적 행동(불연속적)이고, 이 행동들의 집합이 크지 않다면, 이전 챕터에서 언급된 방법들을 사용할 수 있다.

Greedy Q Action

행동을 선택할 때는, 각 행동들에 대한 $Q_t(s,a)$ 들을 구하고, 가장 가치가 좋은 행동을 선택하는 방법이 있으며,

$a ^* _t = arg \ max _a Q _t (s_t, a_t )$

Policy Improvement : off-policy Greedy

Policy Improvement 는 off-policy 방법에서는 estimation policy 를 greedy 하게 변경하고,

on-policy 방법에서는 같은 정책에서 선택되고, off-policy 에서는 임의의 정책에서 선택된다.

Policy Improvement : on-policy $\epsilon$-greedy

on-policy 에서는 $\epsilon$ greedy 등의 방법으로 이루어 진다.

Action from Estimate Policy : on-policy

on-poicy 방법에서 행동은 같은(?) 정책에서 선택 된다.

Action from Behavior Policy : off-policy

off-policy 방법에서 행동은 임의의(?) 정책에서 선택 된다.

Control Algorithms for on-policy and off-policy

Linear Gradient Descent Sarsa($\lambda$) with binary features $\epsilon$-greedy

figure 8.8

gradient descent Q ($\lambda$)

figure 8.9

8.8, 8.9 Control Function Approximation

• binary feature
• $\epsilon$-greedy policy

그림 8.8 , 8.9 는 on-policy sarsa , off-policy q-learning 의 함수 추정을 사용하는 control 방법이다.

모두 선형 방법이며, tile coding , Kanerva coding 과 같은 이진 feature 를 사용했다.

두 방법 모두 행동을 선택하기 위해 $\epsilon$-greedy policy 를 사용 했다.

더욱이 Sarsa 방법은 그것을(?) GPI 를 위해 사용 했다. (?)

두 방법 모두 상태와 가능한 모든 행동들에 대한 present(?) feature $F_a$ 의 집합을 계산했다.

만약 각 행동들에 대한 value function 이 같은 feature 들의 분리된(?) 선형 함수이면, 각 행동들에 대한 $F_a$ 의 색인 번호는 같아서 계산 과정을 간단하게 한다. (?)

Replacing Trace with Function Approximation

Replacing Trace : just trace = 1

위에서 언급한 모든 방법은 'accumulating eligibility trace' 를 사용해 왔다.

비록 'replacing trace' 은 table 방법에서 이점이 있다고는 하지만, 함수 추정에 바로 적용하기 어렵다.

replacing trace 는 어떤 상태를 방문할 때마다 trace 값을 1 증가시키는 것이 아니라 그냥 1 로 설정하는 방법이다.

Feature Trace = 1 in Function Approximation

하지만, 함수 추정 방식에서는 각 상태 마다 trace 를 할당 할 수 없고, 다만, $\vec \theta$ 벡터가 여러 상태들을 아우른다.

이진 feature 를 사용하는 선형 경사 하강 방법에서 feature 들을 replacing trace 들을 위한 상태인 것처럼 처리하면, 이를 해결할 수 있다.

이 방법은 i 번째 feature 를 가지고 있는 상태에 도달할 때마다, i 번째 feature 의 trace 를 accumulating trace 방법에서 처럼 1 씩 증가시키는 것이 아니라 1로 설정 하는 것이다.

Init Trace = 0

state-action trace 로 작업시, 선택되지 않은 모든 상태의 행동들의 trace 를 0 으로 설정하는 것이 일반적이다.

이 또한 이진 feature 를 사용하는 함수 추정 방식으로 확장할 수 있다.

먼저, 어떤 상태에 도달하면, 선택되지 않은 상태와 행동들에 대한 feature 의 trace 를 0으로 설정하고, 선택된 상태와 행동들에 대한 feature 의 trace 를 1 로 설정한다.

테이블 방식에서 언급한 것처럼 이 방식이 replacing trace 를 사용할 때 최선은 아닐 수 있다.

Sarsa 알고리즘에서 선택되지 않은 행동을 0으로 설정할 수 있는 기능을 포함하여, 두 종류의 trace 에 대한 절차적 상세내용이 그림 8.8 에 주어졌다. (?)

....