Reinforcement Learning

첫번째 이야기

Sutton의 Reinforcement learning을 참고하여 작성하였습니다.

한글로 번역하였을때 본연의 의미가 변한다고 생각하는 RL 용어나 문장은 영어로 표현하였습니다.

Finite Markov Decision Process는 Bandit problem과 달리 다른 상황에서 그 상황에 맞는

action을 선택합니다.

action이 reward에만 영향을 미치는 것이 아닌, 그 다음의 상황과 또는 state,

미래의 reward까지 영향을 줍니다.

Bandit에서는 q*(a)를 Estimate하였는데, MDP 에서는 각 state에서 각 action을 선택했을때 value인

q*(s,a) 를 구합니다. (state 개념의 탄생)

또는 각 state에서 optimal selections를 받은 estimate value V*(s)를 estimate합니다.

1.1 The Agent-Environment Interface

MDPs는 goal을 달성하기 위해 상호작용하는 큰 frame입니다.

여기서 배우고 결정을 내리는 것을 Agent 라고 합니다.

Agent와 상호작용하는 것, agent를 제외한 모든 것을 Environment라고 합니다.

Agent와 Environment가 상호작용을 하면서 agent가 action을 선택하면

Environment는 agent의 action에 응답해 그에 맞는 새로운 상황을 agent 에게 줍니다.

Environment는 agent가 action을 여러번 선택하면서 최대화 하려고 하는

reward도 발생시킵니다.

조금 더 자세하게, agent와 environment가 각 sequence of discrete 한 time steps 마다

상호작용을 합니다. time steps는 t라고 표현하고 time step의 순서는 다음과 같이 표시합니다. t=0,1,2,3,…..

time steps에서의 state, action,reward 의 표기법은 다음과 같습니다.

각 time step t 마다, environment의 표현하는 state를 받습니다. St∈ S.

agent는 action을 선택하고 At∈ A(s)

한 step 뒤에,

action의 결과로 agent는 reward를 받습니다. Rt+1 ∈ R ⊂ R

그리고 새로운 new state 를 찾습니다! st+1.

MDP 와 agent는 다음과 같은 sequence 혹은 trajectory를 만듭니다.

finite MDP, 집합 states, actions, rewards (S,A and R)은 finite number of elements 로

이루어져 있습니다.

이 케이스에서는, random variable인 Rt와 St는 오직 앞의 state와 action에 따라 달라지는

discrete probability distribution 입니다.

이 random variables (s’∈S, r ∈R) 은

한 스텝 전의 St-1= s 에서 At-1=a의 action을 선택했을때,

다음 state인 St=s’에서 Rt=r 의 reward가 발생할수 있는 확률 입니다.

St-1 = s에서 At-1=a 를 선택했을때 St=s’ 이고 Rt=r를 받을 확률

모든 s’,s∈S, r∈R, a∈A

함수 p: SxRxSxA -> [0,1]

함수 p는 S,R,S,A 4개의 argument를 받습니다.

“|” 는 조건부 확률의 기호이지만 여기에서는 각 St-1=s에서 At-1= a를 선택했을때의

확률분포를 나타냅니다.

s∈S, a∈A(s) 일때 s’,r을 받을 수 있는 확률은 1 이라는 뜻입니다.

s,a일때 s’,r이 나올 수 있는 모든 가능성은 1이 되어야 합니다.

다음 Equation은

St-1=s, At-1=a 의 Joint Probability의 조건이 주어졌을때,

marginal probability의 sum rule을 이용하여 St=s’일때의 확률을 구할수 있습니다.

이 확률을 state-transition probabilities 이라고 합니다.

station-action 를 two-argument 함수 r: SxA로 expected reward로 계산할수도 있다

마찬가지로 Marginal probability를 사용하여 state s에서 action a를 하여 next state s’로 갔을때 받을수 있는 모든 expected reward를 sum 한 equation을 위와 같이 표기할 수 있습니다.

마찬가지로, statec-action-next-state 의 tree-argument function r:SxA xS 도 expected rewards로 받을수 있다.

st-1 =s 에서 At-1=a를 선택하고 state가 St=s’ 일때 받는 expected reward의 합 을베이지안을 이용하여 계산 할 수 있습니다.

1.2 Goals and Rewards

Reinforcement Learning에서는, Agent의 목표 또는 goal은

Environment에서 agent로 전달되는 reward의 신호를 formalized 하는 것 입니다.

각 time step마다 받는 reward는 숫자이고, Rt∈R 라고 쓸수 있습니다.

RL에서 agent의 goal은 받을수 있는 총 reward의 크기를 최대화하는 것입니다.

주의할점은,

바로 앞에서 받을수 있는 reward를 최대화 시키는 것이 아닌

long run에서의 축척된 reward를 최대화시키는 것 입니다.

“reward hypothesis:

That all of what we mean by goals and purpose can be well thought of as the maxilization of the expected value of the cumulative sum of a received scalar signal(called reward)”

agent는 항상 reward를 최대화 시키기 위해 배울것 입니다.

agent가 이렇게 reward를 최대화해서 우리의 goal을 얻기위해 항상 reward를 provide해줘야 합니다.

The reward signal is your way of communicating to the robot what you want it to achieve, not how you want it achieved.

1.3 Returns and Episodes

agent의 목표는 long run 하는 동안 누적되는 reward를 최대화하는 것이라고 하였는데요.

이것을 공식적으로 정의한다면?

만약 time step t로 denoted 된 Rt+1,Rt+2,Rt+3… 의 reward의 순서를 받는다면 정확히 어떠한 관점에서 이 순서를 최대화 해야할까?

우리는 expected return의 최대값을 찾는 것이고,

그 return은 Gt로 denoted되며 Gt는reward 순서의 specific function 이다.

Simple하게 이 return은 rewards의 총 합이다.

여기서 T는 마지막 final step이다.

Final step이란 episode라고 불리는 agent와 environment의 subsequences 가 naturally break되는 때입니다.

각 episode가 끝나는 state를 terminal state라고 부릅니다.

Episode의 끝이 승 / 패 에 상관없이,

새로운 episode는 전에 에피소드가 어떻게 끝나는지 무관하게 독립적으로 다시 시작됩니다.

그러므로 episode의 끝은 terminal state로 고려 될 수 있습니다.

Episod에 이런 tasks들을 episodic tasks라고

불립니다.

Episodic tasks에서는 nonterminal states 집합을 S,

모든 state의 집합과 terminal state이 같이 있는 것을 S+,

시간이 terminate 될때를 T

라고 합니다.

또한, 많은 케이스에서 agent-environment 상호작용은 멈추지 않고 계속 진행됩니다.

이런것을 continuing tasks 라고 합니다.

이렇게 T가 infinite로 표시됩니다.

여기서 추가되는 컨셉은 discounting입니다. agent는 action을 선택하여 discounted된 reward의 총 합을 최대화 하려고 시도합니다.

At를 선택하여 dicounted가 적용된 return을 최대화 합니다.

1.4 Unified Notation for Episodic and Continuing Tasks

Reinforcement learning 에는 2가지 tasks가 있습니다.

agent-environment 의 상호작용에서

sequence of separate episodes로 나누어질수 있는것

(episodic tasks) 과

그렇지 않은것 (continuing tasks) 의 종류가 있습니다.

Episodic tasks를 정확히 하려면, 몇가지 추가되는 notation이 있는데요. 하나의 long sequence of time steps 보다는, series of episodes 를 알아야 합니다.

각 episode의 time steps은 0부터 시작합니다. 그러므로 St처럼 time t만 표시해주면 안되고 St,i 처럼 episode의 notation을 추가하여 몇번째 episode인지 representation 해야합니다.

이 그림에서의 검은색 사각형은 episode의 끝을 나타내는데요. S 0부터 시작하여 reward를 +1,+1,+1,0,0,0 의 순서로 받습니다. 이것을 합했을때 T 가 무한이어도 T=3일때와 reward의 합이 같습니다.

R4 이후의 reward가 0이기때문에 discount factor을 적용해도 마찬가지입니다.

그래서 기존의 Gt공식을 변형하여

episodic tasks와 continuing tasks 에서 같이 쓸수 있는 Equation으로 바꿔줍니다.

이 공식을 사용합니다.

1.5 Polices and Value Function

거의 모든 RL 알고리즘은 value function 을 estimate하는 것이다.

agent가 주어진 state에서의 how good 을 측정하는 것!

여기서 “how good”의 정의는, expected 한 미래의 reward입니다.

어떻 action을 선택하냐에 따라 미래의 rewards는 달라질 것 입니다.

따라서,

value function은 acting에 따라 변합니다.

Policy는 state에서 각 가능한 action을 선택할 확률을 mapping 한 것입니다.

만약 agent가 time step t를 진행하며 policy π를 따랐을때, π(a|s)

은 St=s 일때 At=a 의 확률입니다.(s의 state에서 a 의 action을 할 확률)

p 함수와 같이, π 은 일반적인 함수 입니다.

π(a|s)에 있는 “|”은 각 s∈S에 a∈A의 확률분포입니다.

RL에서는 agent가 경험의 결과에 따라 π가 변합니다.

Policy π를 따른 Vπ(s)은 s에서 시작하고 policy π를 따라서 action을 하며 얻은expected return입니다.

MDPs, 에서 Vㅠ는 fomal하게 다음과 같이 정의됩니다.

St가 s부터 시작하여 policy를 따라 받은 reward의 총 합(Gt)을 expected한 값 ,

policy π를 따라 St=s 부터 Terminal state까지의discounter factor를 적용한 reward를 모두 합한 것 입니다.

E[]은 agent가 주어진 policy π를 따랐을때 받는 expected value of a random variable이고, t는 어떠한 time step 입니다.

Terminal state의 value는 항상 zero 이어야 하고,

이런 Vπ함수를 state-value function for policy π 라고 부릅니다.

비슷하게, policy π를 따르고, state s 에서 action a를 선택하며 얻은 reward의 합을 qπ(s,a)라고 denoted합니다.

s에서 시작하여, policy ㅠ를 따라 action a를 선택하고받은 reward의 expected 를 return 합니다.

이 qㅠ를 action-value function for policy π 라고 합니다.

Value function vㅠ 와 qㅠ는 경험을 통하여 측정 합니다.

예를 들어서,agent가 policy ㅠ를 따라 각 state와 encounter 그 state를 따라가며 실제로 받은 return들을 average합니다.

state가 encounter한 횟수가 무한대에 approaches하게 되면 state value Vㅠ(s)가 수렴 하게 됩니다.

만약 각각의 state에서 선택한 action들을 average한다면action value인 qㅠ(s,a)가 수렴할 것입니다.

이런 예측 방법을 많은 random samples of actual returns를 averaging한 Monte Carlo methods라고 합니다.

하지만 이런 방법은 스테이트가 아주 많아지면 각각의 state를 individually하게 average하는 것은 실용적이지 않습니다.

action, a 는 집합 A(s)으로부터 선택되고, next state s’는 집합 S(혹은 episodic problem 일때 S+로부터) 그리고 rewards r은 집합 R으로부터 가져옵니다.

마지막 equation에 s’와 r의 sum을 s’의 의 모든 value와 r의 모든 value의 모든 value의 가능성을 sum으로 merged 하였습니다.

첫번째로 확률을 계산합니다. π(a|s)p(s′,r|s,a) , brackets에 있는 qunatity를 확률에 의해 weight합니다. 그다음 expected value를 얻을수 있는 모든 probabilities 를 sum over합니다.

이 Equation은 Bellman equation for vπ 입니다.

식은 value of state와 values of its successor states의 relationship 을 express한 식 입니다.

state에서 possible successor states를 looking하고 있다면, state s에서 시작하여, agent는 policy에 따라 action중에 하나를 선택합니다.

주어진 함수 p에 따라 environment는 s’와 r를 response 합니다.

The Bellman equation averages over all the possibilities, weighting each by its probability of occuring

Value function vㅠ는 Bellman equation의 unique solution 입니다.

옆의 Diagram을 Backup diagram으로 부르는 이유는, diagram relationships의 형태가

update or backup의 형태로 보이고 있기 때문입니다.

successor states 혹은 successor state-action pair 로부터 Transfer value information이 state 혹은 state-action pair로 back하게 operate합니다.

1.6 Optimal Policies and Optimal Value Functions

Reinforcement learning을 solving 한다는 것은 long run 동안 reward를 많이 받는

policy를 찾는것 입니다.

Finite MDPs에서는 다음과 같이 optimal policy를 정의합니다.

ㅠ의 expected return이 ㅠ’보다 같거나 더 좋으면

Policy ㅠ 는 policyㅠ’ 보다 같거나 더 좋아야 합니다.

항상 다른 policy보다 좋거나 같은 policy가 존재하고 이런 policy를 Optimal policy라고 합니다. 이런 optimal policy가 하나 이상일수도 있습니다.

optimal policy가 하나 이상이어도,

optimal policies ㅠ*이라고 합니다.

이 optimal policies는 같은 state-value를 share하며, optimal state-value function이라고 부릅니다. v*이라 denoted합니다 .

Action-value function에서는 optimal action-value function,q*라고 denote합니다.defined as

State-action pair(s,a) 함수는 optimal policy π에서 state s 에서 action a 을 선택했을때의 expected return 을 줍니다. 그러므로 다음의 식과 같이 q*를 v*의 term을 사용하여 표기하는것이 가능합니다.

앞의 식인 Bellman equation 과 같은데 action의 given 을 추가하여 q의 형태로 만들은것

v*의 Bellman equation을 Bellman optimality equation이라고 합니다.

Bellman optimality equation은 optimal policy 아래의 value of a state은 state에서 가장 best한 action을 선택해 받은 expected return과 같아야 합니다.

위의 equation 중 마지막 두 equation은

두가지 형태의 v*의 Bellman optimality equation입니다.

q*의 Bellman optimality equation은 아래와 같습니다.

아래의 그림은 v*와 q*의 Bellman optimality equation을 나타내고 있습니다.

vπ와 qπ와 똑같지만 max를 나타내주는 호가 추가가 되어 있습니다.

Reference:

Reinforcement Learning : An Introduction (Richard S. Sutton, Andrew G. Barto), MIT Press, 1998.