3.1 The Agent-Environment Interface
RL Problem: 목표를 달성하기 위한 상호작용을 통해, 학습하는 문제에 대한 간단한 틀
- agent: learner or decision-maker
- environment: interact with outside the agent. provide reward
- reward: numerical value that the agent tries to maximize
- policy: 각 time-step에서 agent가 해당 state에서 possible action를 선택하는 기준. πt(a|s): St = s에서 At = a인 확률
agent between env, continually interact
: agent가 action를 선택하고, 환경은 해당 action에 response하여 new env를 agent에게 전달한다.
interaction process
set descrete time-steps(t, t+1, t+2 ...)
1. agent가 env의 representation인, possible states 중 하나의 St를 받음
2. state St에서의 available actions 중 하나인 At를 선택
3. next time-step 후에 agent는 At의 결과로, numerical reward인 Rt+1와 new state인 St+1를 받음
agent's goal: 장기적인 관점에서의 total reward의 최대화
RL methods: experience의 결과에 따라 agent가 policy를 어떻게 update할 것인지에 대한 방법론
aspect of RL
: abstract, flexible하여 다양한 문제에 다양한 방법으로 적용이 가능하다.
- time step는 real time의 간격으로 고정될 필요가 없다.
: time step은 decision-making과 acting에 필요한 임의의 successive stages로 설정 가능하다.
- action와 state는 다양한 form으로 표현될 수 있다.
: 단순하고 직관적인 low-level이나 추상적이고 상징적인 high-level로 결정되어진다.
- agent와 env의 경계는 실제로 생각하는 물리적 경계와 다르다.
: 경계는 주로 agent에 더 가깝게 그려지며, 실제 동작하는 모델 내에 action, reward가 존재한다고 하더라도 agent의 외부로 간주된다. agent가 임의로 변경 할 수 없는 것은 외부에 있는 것으로 간주되어 env의 일부로 간주된다. (agent를 실제 동작 모델이라고 생각하면 안된다.)
- agent가 env의 전체를 안다고는 가정하지 않는다.
: agent는 reward를 구하는 방식에 대해 일부를 알고있긴 하지만, reward 계산은 agent가 보는 이상의 것을 필요로 하므로 항상 agent 외부에 있다고 간주한다. (실제로 agent가 env에 대해 모든 것을 알고 있어도 문제를 해결하지 못하는 경우가존재한다. )
- complicated problem에는 multi-agent가 동작하는 경우도 있다.
: low-level agent의 part of state를 토대로 high-level agent가 action를 결정한다. 실제로 agent-env 경계는 states, actions, rewards를 선택하고, 관심있는 decision-making task를 식별하면 결정된다.
3 signals about goal-directed behavior 3 signals
- actions: to represent the choices made by the agent
- states: to represent the basis on which the choices are made
- rewards: to define the agent’s goal
위 3 signals는 모든 decision-making 학습 문제를 표현하는데 충분하지 않을 수 있지만 usefull하고 widely applicable하다.
states와 actions는 example마다 모두 다르며 어떻게 표현되는지에 따라 performance가 달라질 수 있다.
3.2 Goals and Rewards
Objective
: maximization of expected value of cumulative sum of a received scalar signal(reward)
우리는 agent가 목표를 달성하게 하기 위해 reward를 제공해야 하는데, 따라서 설정한 reward가 성취하고자 하는 것을 진정으로 나타내는 것이 중요하다. reward는 모델이 달성하고자 하는 방식이 아니라 달성하고자 하는 것을 모델에 전달하는 방법을 의미한다.
reward를 정의하는데 있어서 reward가 agent가 아닌 env에서 계산된다는 것을 명심해야 한다.
우리가 이렇게 하는 이유는 agent의 궁극적인 목표가 imperfect control를 가져야 하기 때문이다. 자신의 행동을 임의로 변경할 수 있는 것과 같은 방식으로 보상을 받았다고 단순히 선언 할 수 없어야 한다. agent 외부에 reward를 배치함으로써 이것은 agent가 일련의 내부 보상을 스스로 정의하는 것을 배제하지 않는다.
3.3 Returns
time step t 지남에 따라 받은 reward가 Rt+1, Rt+2, Rt+3... 식으로 진행된다고 했을 때
우리는 expected return Gt를 위와 같이 정의한다.
Gt는 reward sequence의 function으로 정의되고 간단한 경우는 return은 reward의 합계이다.
t부터 T까지의 최종 시간동안의 sequence를 episode라고 부르고 terminal state에서 종료된다.
종료된 후에는 statring state에서 재설정되어 episode가 재시작된다. episode task를 수행할 때 다음의 정의를 잘 확인해야 한다.
- S: set of nonterminal states
- S+: set of all states plus the terminal state
그러나 많은 경우에 agent-env interation는 identifiable episode로 구분되지 않고 cotinually하게 진행된다.
따라 Gt에서의 최종 시간인 T=∞이고, 최대화 하려는 return이 무한해지는 상황에 도달한다. 따라서 우리는 discounting이라는 개념을 사용하여 미래에 받을 discounted reward가 최대화되는 action을 선택하려고 한다.
- γ(discount rate): a parameter, 0 ≤ γ ≤ 1. determines the present value of future reward
미래의 k 시간에서의 reward는 γ^(k-1)로 표현되며 γ의 size에 따라 training 방식의 차이가 존재한다.
- γ = 0: 즉각적인 reward를 최대화므로 'short-sighted'이다. Rt+1의 값만 최대화하기 위해 현재 St에서의 At를 선택한다.
- γ = 1: 미래의 reward에 대해 고려하므로 'far-sighted'이다. 그러나 short-sighted 방식으로 행동하면 미래에 대한 reward가 줄어들 수 있기 때문에, γ가 1에 가까울수록 agent는 return에 대해 더 고려하여 At를 선택한다.
3.4 Unified Notation for Episodic and Continuing Tasks
episode가 episodic한 경우와 continous한 경우가 모두 존재하기 때문에 둘을 동시에 표현 할 수 있는 표기법이 필요하다.
- 하나의 긴 sequence보다는 episode i를 one-step마다 고려해야 한다.
: 따라서 St,i와 같이 표현해야 하지만 서로 다른 i를 고려해야할 필요가 없다는 것이 증명되어 항상 single episode만을 언급한다.
- 유한한 수의 항과 무한한 수의 항을 합치기 위해서 episode 종료 시, reward가 0으로 가는 loop로 표현한다.
: 아래 그림의 사각형은 특정 episode가 먼저 종료시에 전체 무한 sequence를 합산해도(discount 고려해도) 동일한 수익을 얻는다.
따라서 위 조건을 고려하여(T = ∞ or γ = 1인 가능성을 모두 포함하여) 다음과 같이 표현이 가능하다.
3.5 The Markov Property
characteristic of state
- state는 이전 state와 함께 과거 정보를 기반으로 구성되고 유지된다.
: state의 표현을 즉각적인 정보로만 이해하지 않고, state가 이전 정보까지도 포함한다고 예상해야 한다. 이때 즉각적인 정보 이상의 것을 요구하지만, 모든 과거 정보의 history를 요구하지는 않는다.
- state는 env에 대한 모든 정보를 agent에게 알려주지 않는다.
: 모든 경우에 env에 숨겨진 state가 있지만 agent는 fully observable하지 않다.
what is Markov property?
Markov Property: env와 state를 정의하는 속성. 모든 과거 정보에 대한 history를 유지하는데 성공한 state를 'Markov하다'라고 함.
- 따라 중요한 모든 정보가 현재 state에 위치하기 때문에 'independence of path' 속성이라고도 한다.
: 현재 state는 path or history로 이어진 신호와는 무관하다는 것을 의미한다.
시간 t+1에서 시간 t에서 취해진 action에 대해 어떻게 반응하는지 고려해보자.
일반적인 경우 아래와 같이 완전한 확률 분호를 지정해야만 정의가 가능하다.
그러나 state가 Markov한 경우 r, s' 및 history의 모든 값인 S0, A0, R1 ... Rt, St, At로 표현될 때, t+1에서 env response가, t에서의 St와 At에만 의존하고, env와 작업 전체도 Markov하다고 할 수 있다. 이 경우에는 다음과 같이 정의된다.
env가 Markov한 경우, 현재의 St와 At가 주어진다면 다음 St+1와 next reward를 예측할 수 있다.
따라서 이 위 방정식을 반복할 때, 현재 complete history가 주어진다면 현재 State에 대한 정보로 미래의 모든 state와 reward 예측이 가능하다. 따라 Markov property는 state가 선택할 수 있는 best action을 선택할 수 있는 기반을 제공한다는 것 또한 알 수 있다.
importance of Markov property
Markov property는 decision과 value가 현재 state의 function으로만 가정되기 때문에 RL에서 매우 중요하다
이 속성이 informative하고 effective하게 사용하기 위해서는 state representation 또한 명시적이어야한다.
일반적인 알고리즘 이론들은 Markov property를 가정하고 진행되지만, 모든 이론이 적용될 때 Markov property가 엄격하게 적용되어야하는 것만은 아니다. 즉, 만약 state가 Markov하지 않더라도 RL learning을 Markov 상태의 근사치로 생각하는 것이 적절하다.
3.6 Markov Decision Processes
MDP: reinforcement learning task that satisfies the Markov property
finite MDP: state/action space가 finite한 MDP. 대부분에서 취급
특정 finite MDP는 state, action set와 env의 one-step 동작에 의해 정의된다. 어떤 state, action이 주어지면, 가능한 next state인 s', next reward인 r에 대한 확률이 표기된다.
이러한 수식이 finite MDP 동작을 완벽히 정의하고, 앞으로의 이론이 finite MDP라고 암시적으로 가정한다.
representation of entity based on MDP
finite MDP 동작이 정의되고, 환경에 대해 알고 싶은 다른 것들이 계산가능하다.
3.7 Value Functions
RL에서 우리는 얼마나 좋은지에 대한 개념은 expected future reward의 관점에서 정의된다. 물론 agent가 앞으로 받을 reward는 어떤 action을 취할 것인지에 따라 달라지고 value function은 특정 policy에 연관되어 정의된다.
terminal state의 value는 언제나 0이다.
- π(a|s): St = s에서 At = a를 선택할 확률
- Eπ[ ]: agent가 policy π를 따르고, t가 임의의 time-step인 경우 임의 변수의 expectation
- Vπ(s): policy π에서 state s에서의 value(expected return). state-value function
- Qπ(s,a): policy π에 대한 state s에서의 action a를 했을 때의 value(expected return). action-value function
- Vπ, Qπ는 experience을 통해 추정이 가능하다.
: agent가 policy π로 state를 무한번 만날 때마다 해당 state St를 지났을 때의 actual returns의 평균을 유지하고 있다면, state-value function으로 수렴된다. Qπ도 이와 유사하게 state가 가진 action At마다 각각의 평균을 유지한다면 Qπ로 수렴된다.
이러한 방식의 estimation method를 Monte-Carlo라고 부른다.
MC: actual return에 대한 무작위 sample의 평균을 계산
- 그러나 수많은 state에서 개별적으로 평균을 유지하는 것은 실용적이지 않다.
대신 agent는 Vπ, Qπ를 매개변수화 된 함수로 유지하고 observe된 actual return과 더 잘 일치하도록 매개변수를 조정한다. 이는 매개변수화된 function approximator의 특성에 따라 다르지만 정확한 estimate를 산출할 수도 있다.
A fundamental property of value functions
RL 및 DP 전체에 사용되는 value function의 기본 속성은 특정 recursive relationship을 충족한다.
: policy π 및 states에 대해 다음 일관성 조건이 current St value와 next St+1 value 사이에 유지된다.
- Bellman Equation: value of state와 values of 후속 state의 관계.
마지막 방정식에서 우리는 현재의 r과 s'의 value 합계로 value function을 표현했다. a, s', r의 3가지의 모든 값의 합이다.
각 state-action-next-state의 triple에 대해 π (a|s) p (s',r|s,a)의 확률에 따라 계산하고, 해당 확률만큼 괄호안의 값에 비중을 부여한 다음 expected value를 얻기 위해 모든 가능성을 합산한다.
backup diagram
RL learning의 핵심인 update or backup operation 과정을 표현하기 위해서 다음의 diagram을 사용한다.
open circle: state / solid circle: state-action pair
start state S는 몇가지의 action을 취할 수 있다. 이 상태에서 env는 다음 state 한가지의 s'을 r과 함께 응답한다.
- Bellman equation은 발생 확률에 비례하여 모든 가능성을 평균시킨다.
: operation는 후속 state'/state-action pairs'에서 value information를 앞쪽의 state/state-action pairs로 전송한다.
(이 때, backup diagram node는 후속 state가 현재 state인 경우가 있듯이 반드시 distinct state가 아닐 수 있다. )
3.8 Optimal Value Functions
RL learning의 목적은 장기적인 reward를 maximize하는 policy를 찾는 것을 의미한다.
Value function은 policy에 대한 partial ordering을 정의해준다.
- policy π >= policy π'면, 모든 state s에 대하여 Vπ(s)>=Vπ'(s)
항상 다른 policy보다 더 좋거나 같은 policy가 최소 한개는 존재한다.
- Optimal policy: 몇가지의 policy가 있을 수 있지만 우리는 optimal policy를 π*로 표기한다.
optimal policy들은 같은 value function을 공유하고 다음 수식으로 표기된다.
- V*(s) = max Vπ(s), optimal state-value function
- Q*(s,a) = max Qπ(s,a), optimal action-value function
- Q*를 V*의 측면에서 표현할 수 있다.
V*가 policy에 대한 value function이기 때문에, 기존의 Bellman equation의 state value에 대한 재귀 특성을 만족한다.
직관적으로, Bellman optimality equtaion는 optimal policy에 따른 state의 value가 해당 state에서의 best action에 대한 expected return과 같아야 한다는 것을 표현한다.
optimal value function이기 때문에, 아래의 특별한 형태로 식이 표현된다.
diagram으로 표현하면 다음과 같다.
3.9 Optimality and Approximation
- optimal policy를 구한다는 것은 실제로는 매우 어렵다.
: extreme computational cost를 통해서야만 optimal policy가 만들어지기 때문이다.
env dynamics에 대한 accurate, complete model를 가지고 있다고 해도, Bellman optimality equation을 푸는 것을 통한 방법으로는 쉽게 optimal policy가 계산되지는 않는다. 극히 일부분의 experience로는 model이 optimal action를 행하게 만들 수 없다.
따라 agent가 직면한 문제의 중요한 측면은 single time-step에서 수행될 수 있는 양의 계산 능력을 가지고 있느냐 이다.
- 메모리 가능성은 중요한 제한사항이다.
: value function, polices, models의 approximation를 구하기 위해 큰 메모리가 필요하다.
- tabular case: small, finite state sets를 가지고 있을 때는, array or table를 이용하여 각각의 state/state-action pair의 근사치를 형성할 수 있다.
그러나 실질적인 경우에는 tabular entity보다 더 많은 state가 존재할 수 있기에, 이를 위해서 좀 더 간결하게 매개변수화 된 function representation을 사용하여 approximate시킨다.
- 결국 우리는 RL problem을 해결하는데 있어서 approximation을 사용하게 된다.
: RL on-line 특성은 자주 접하는 state에 대한 적은 노력으로 더 좋은 결정을 내리기 위해 더 많은 노력을 기울이는 방식으로 optimal policies를 approximate 가능하게 한다.
web.stanford.edu/class/psych209/Readings/SuttonBartoIPRLBook2ndEd.pdf
'논문 리뷰 > RL' 카테고리의 다른 글
| DRQN1 (0) | 2021.05.12 |
|---|---|
| DRQN (0) | 2021.03.25 |
| 04. Dynamic Programming (0) | 2021.03.22 |
| Vanila Actor-Critic (0) | 2021.03.09 |
| REINFORCE(MC-PG) + vanila Policy Gradient (0) | 2021.03.04 |
| Lecture 7: Policy Gradient (0) | 2021.01.23 |
댓글