sutton 교수의 Reinforcement Learning An Introduction을 읽고 공부하기
chapter 3 요약하기
이번 챕터에서는 finite Markov Decision Process의 문제를 소개한다. MDP는 연속적인 decision making을 공식화한 것으로 연속적인 decision making이란 에이전트가 지금 선택한 action이 즉각적인 reward뿐만 아니라 그 후의 상황, state, 미래의 reward에까지 영향을 미치는 것을 의미한다.
MDP는 강화학습문제에서 수학적으로 이상적인 형태로 핵심적인 요소들로는 return, value function, Bellman equation같은 것들이 있다. 우리는 finite MDP로 공식화할 수 있는 예제들을 볼 것이다.
다음은 MDP로 강화학습을 풀기 위해 우리가 살펴봐야하는 요소들을 나열했다.
에이전트와 환경
MDP는 목표를 달성하기 위해 상호작용을 통해 학습하는 것을 하나의 프레임처럼 만든 것이다. 여기서 learner와 decision maker를 이제부터 에이전트(agent)라 부르고 에이전트의 밖에서 에이전트와 상호작용하는 것들을 환경(environment)라 부른다. 에이전트는 action을 선택하고 환경이 action에 대한 상황(situation)을 에이전트에게 알려준다. 그러면 환경은 이 action에 대한 reward를 에이전트에게 주고, 에이전트의 목표는 reawrd가 최대가 되는 법을 찾는 것이다.
그림 3.1을 통해 이를 더 정확하게 표현하자면, 이산적인 시점 t마다 에이전트는 환경에게서 어떤 state인지를 알게 되고 그것을 기반으로 action을 선택한다. action을 선택한 후에는 다음 시점 t+1에 에이전트는 reward를 받고 새로운 state를 알게된다. 이를 다음과 같은 순서로 나타낼 수 있다.
Finite MDP문제에서 state, action, reward들의 집합은 모두 유한집합이고 state가 markov propery를 사용한다고 가정하면, 어떤 state s에서 action a를 선택했을 때 환경으로 부터 받는 state s'과 reward r은 다음과 같이 확률로 표현할 수 있다. 가운데의 '|'를 보면 알 수 있듯 조건부 확률이다. 나중에 나오지만 이런 dynamic function을 알고 있다는 것은 환경에 대한 완벽한 정보를 알고있음을 말해준다.
여기서 함수 p를 MDP의 dynamics라고 정의한다. 아래와 같은 표현은 state s에서 action a를 선택했을 때 에이전트가 갈 수 있는 다음 state s'과 그 때 받을 수 있는 reward r은 확률적으로 다양할 수 있고 그 모든 확률들의 합은 1이다 라는 것을 나타낸다.
위의 4개의 아규먼트를 가지는 dynamic function p에서 state-transition 확률이라는 환경에 대한 다른 정보를 계산할 수 있다. 이는 dynamic function에서 3개의 아규먼트만을 사용해서 다음과 같이 표현한다.
또한 두개의 아규먼트만을 사용해 state-action 쌍의 reward의 기대값을 계산할 수 있다.
그리고 세개의 아규먼트를 사용해 state-action-next state의 reward의 기대값을 계산할 수 있다.
에이전트와 환경 사이의 경계는 전형적인 물리적 경계가 아니다. 이 경계를 정하는 일반적인 규칙은 에이전트가 임의로 바꿀 수 없는 것들을 환경의 일부라고 생각하는 것이다. 에이전트-환경의 경계는 에이전트가 어느정도를 아느냐의 지식이 아닌 에이전트가 컨트롤할 수 있는 범위를 넘어서는 것을 환경으로 한다.
MDP 프레임워크는 에이전트-환경의 상호작용으로부터 학습하는 목표지향적인 문제를 상당히 추상화시킨 것으로 MDP는 달성하려는 목표가 무엇이던지 에이전트와 환경 사이의 세가지 신호로 줄일 수 있다고 제안한다. 하나의 신호는 에이전트에 의해 선택되는 것(action), 이 action을 기반으로 만든 신호(state), 에이전트의 목표(reward)이 세가지다. MDP 프레임워크는 모든 decision-learning 문제들을 만족시킬만큼 유용하진 않지만 상당히 유연하고 유용하다.
Golas and Rewards
강화학습에서 에이전트의 goal은 reward라는 에이전트에게 가는 특별한 신호로 공식화한다. 에이전트는 장기적인 시간에 걸쳐 쌓인 reward의 총합을 최대화하는 것을 학습해야 한다. 이렇게 reward signal을 사용하는 것은 강화학습의 가장 구분되는 특징이다.
reward signal을 goal로 공식화하는 것은 제한적으로 보일 수 있지만, 실제로는 유연하고 광범위하게 적용할 수 있다. 예를 들어 로봇이 걷는 것을 학습할 때, 각 시점마다 로봇이 앞으로 걸어간 것에 비례해 reward를 준다던가, 미로를 탐색하는 로봇에게 탈출하기 전까지 매 시점마다 -1을 reward를 주는 방법으로 학습시킬 수 있다.
이런 예제들에서 에이전트는 항상 reward를 최대화하는 법을 학습한다. 그러기 위해서는 우리가 달성하기 원하는 방향으로 에이전트에게 줄 reward를 설정하는게 매우 중요하다. 예를 들어 체스게임 에이전트는 상대의 말을 땄을 때 같은 부가목표가 아니라 실제로 이겼을 때 reward를 받아야한다. 이런 부가목표에 도달했을 때 reward를 받으면 에이전트는 실제 목표가 아닌 부가목표를 달성하는 법을 찾으려고할 것이다. 우린 reward signal을 통해 로봇이 어떻게(how) 목표를 달성하기 원하는지가 아닌 무엇(what)을 달성하기 원하는지를 알려줘야 한다.
Returns and Episodes
에이전트의 목표는 장기적인 학습에서 받은 누적 reward들의 총합을 최대화하는 것이라고 얘기했다. 우리는 이 reward들의 최대값, 즉 expected return을 최대화하는 방법을 찾을 것이다. expected return은 \( {G}_{t} \)로 표기하고 다음과 같이 reward의 sequence로 함수를 정의한다.
수식 3.6에서 T는 마지막 시점으로 이 T는 episode마다 다양한 값이 존재한다. 에이전트-환경의 상호작용에서 얻는 reward들의 합은 위와같이 표현하고 이걸 episode(or trial)라고 부른다. 각 episode는 terminal state로 끝이나고 다시 starting state에서 시작한다. episode가 어떤 방식으로 끝나든 이전 episode와 독립적으로 다시 시작하기 때문에 각각의 episode는 모두 이전의 episode과 다른 결과와 다른 reward를 주지만 동일한 terminal state로 끝이 난다. 이런 종류의 episode가 있는 task를 episodic task라 한다.
한편 모든 에이전트-환경 상호작용이 자연스럽게 에피소드로 나눠지진 않는다. 예를 들어 수식 3.6에서 \(T = \infty \)라면 이는 continuning task라 부르고, 이런 continuing task에서는 expected return이 너무 쉽게 최대화되기 때문에 수식 3.6은 적합하지 않다. 그래서 discounting이라는 개념을 새롭게 도입한다. \( \gamma \)는 [0, 1]의 범위에 있는 discount rate로 이를 적용한 식은 아래와 같이 표현한다.
이 discount rate는 미래에 받을 reward의 현재 가치를 결정한다. \( \gamma \)는 기본적으로 0~1사이의 값이기 때문에 미래에 받는 reward일 수록 거듭제곱을 많이해서 현재의 가치는 낮아지게 된다. 만약 \( \gamma \)=0이면 에이전트는 즉각적인 reward를 최대화하면서 학습하겠다는 뜻이 된다. 이와 반대로 \( \gamma \)가 1에 가까워질수록 에이전트는 미래에 받을 보상을 더 많이 고려하겠다는 뜻이 된다. 한 편 위의 식은 조금 다르게 쓸 수도 있다.
수식 3.8은 연속적인 시점 t, t+1의 return은 서로 연관되어 있음을 보여준다.
Episodic task & continuing task
앞에서 episodic task와 continuing task가 있음을 봤다. 앞의 경우는 각 action이 에피소드에서 유한한 reward에 영향을 주기 때문에 더 쉽다. 이러나저러나 두 경우를 모두 다뤄야하기 때문에 하나의 표기법을 제안한다. 일반적으로는 time t 뿐만아니라 episode i도 같이 표기를 해야하기 때문에 \( {S}_{t, i} \)와 같이 표시해야하는데, 일단 우리는 특정 단일 에피소드에 대해서만 고려를 할 것이기 때문에 \( {S}_{t} \)와 같이 줄여서 쓴다.
Episodic과 continuing task를 둘다 표현하는 단일 표기법을 사용하기 위해서는 다른 규칙이 필요하다. 이를 위해 두 task모두 에피소드의 terminal state를 오직 reward로 0만 주는 특별한 absorbing state에 들어가는 것으로 해 통합할 수 있다.
여기서 검은색 사각형이 absorbing state로 에피소드의 끝이다. 만약 episodic task가 설정한 최대 T를 넘어간다면 그 이후의 reward들은 모두 0으로 한다. 그러면 T=3인 episodic task에서는 그림과 같이 +1, +1, +1, 0, 0, 0, ...과 같은 reward sequence를 얻을 것이다. 결국 이 sequence는 무한히 이어져도 T=3이후는 모두 reward가 0이기 때문에 동일한 return을 얻을 것이다. 이는 continuing task에서 discouning을 적용해도 똑같다. 그래서 보통 return은 수식3.7처럼 쓴다. 다만 대안적으로 \( T=\infty 또는 \gamma=1 \)인 가능성을 포함하게 다음과 같이 식을 쓴다.
Policy and Value function
거의 모든 강화학습 알고리즘들은 에이전트가 해당 state에 있는게 얼마나 좋은지를 계산하는 value function(state의 function 또는 state-action 쌍의 function)이 있다. 여기서 "얼마나 좋은지"는 바로 앞에서 배운 reward의 기대값, expected return으로 정의한다. 당연하게도 미래에 받을 것이라 기대하는 reward는 에이전트가 어떤 action을 할지에 달려있기 때문에 value function은 policy에 의해 정의 된다.
공식적으로 policy는 어떤 state에서 action을 선택할 확률로, 에이전트가 time t에서 policy \(\pi\)를 따르면 \(\pi \left( a|s \right) \)로 나타낸다. 이는 에이전트가 state s에서 action a를 할 확률이라고 해석할 수 있다. 그리고 이런 policy \(\pi \)의 영향 아래에 있는 state의 value function은 \( {v}_{\pi} \left( s\right) \)로 표시한다. \( {v}_{\pi} \)는 MDP로 다음과 같이 공식화 한다.
수식 3.10에서 \( {v}_{\pi} \left(s \right) \)를 policy \(\pi \)의 state value function이라 한다. 수식을 보면 어떤 state s에서 받을 수 있는 reward들의 총합(return)의 기대값으로 표현한 것을 알 수 있다. 여기서 terminal state는 항상 0이다. 이와 비슷하게 state s 에서 action a를 선택했을 때의 value를 \({q}_{\pi} \left(s,a \right)\)라 하고 다음과 같이 식을 쓴다.
이런 state value function이나 action value function은 에이전트가 policy \(\pi \)를 따르며 받는 return들의 평균을 계속해서 계산하며 구한다. 이렇게 에이전트가 실제로 받는 값들의 평균으로 계산하는 방법을 Monte Carlo 방법이라 부르고 나중에 다룰 것이다.
강화학습과 다이내믹 프로그래밍에 사용되는 value function의 근본적인 특성은 return을 계산하기 위해 우리가 위에서 사용했던 수식3.8과 유사한 재귀적 관계를 만족하는 것이다. 그래서 다음과 같이 쓸 수 있다.
이를 간단하게 생각해보면 어떤 state s에서 선택할 수 있는 모든 action a와 그 때의 다음 state인 s', reward인 r 그리고 다음 state의 value function인 \( {v}_{\pi}\left(s' \right) \)를 모두 고려해서 계산한게 현재 state s의 value function이라는 뜻이다.
아래의 다이어그램은 state와 그 다음 state를 그림으로 보여준 것이다. 여기서 흰원은 state를 검은색 원은 state-action 쌍을 나타낸다. 현재의 state s에서 시작해서 에이전트는 policy \(\pi \)를 따라 다이어그램에서 보이는 세가지 action을 선택할 수 있다. 각 aciton 중 하나를 선택하면 환경은 function p로 나타낸 dynamics를 참고해 에이전트에게 다음 state s'과 reward r을 알려준다. 수식 3.12의 방정식은 \({v}_{\pi} \)의 벨만방정식으로 현재 state와 다음 state 간의 관계를 말해주는 방정식이다. 밑의 다이어그램으로 벨만방정식을 더 잘 이해할 수 있다.
위와 같은 다이어그램을 백업 다이어그램이라고 부르는데, 왜냐하면 다이어그램 내에서의 관계가 강화학습의 핵심인 backup operation에 기반을 두고 있기 때문이다. 그림을 보면 다음 state s'은 이전 state인 s에 value information을 전송한다.
Optimal policy and optimal value function
강화학습 문제를 푼다는 것은 장기적인 학습에서 많은 reward를 받게 해주는 policy를 찾는 것이다. policy \(\pi \)의 모든 state에 대한 expected return값이 policy \( \pi' \)보다 크거나 같으면, \( \pi \geq \pi' \)이고 이는 곧 \( {v}_{\pi}\left(s \right) \geq {v}_{\pi'}\left(s \right) \)와 같다. 항상 적어도 하나의 policy의 value function은 다른 모든 policy의 value function보다 같거나 크다는 얘기이다. 바로 이 policy가 optimal policy다. optimal policy는 \( {\pi}_{*} \)로 표시하고 이 때의 value function은 \( {v}_{*} \)라고 표시한다.
수식 3.13을 보면 optimal policy는 어떤 상태 s에서 가장 높은 value function을 주는 policy임을 알 수 있다. state 뿐만 아니라 action value function에도 다음과 같이 적용할 수 있다.
그리고 action value function은 다음과 같이 next state value funtion을 이용해 쓸 수도 있다.
위의 optimal action value function을 이용해 optimal state value function을 다음과 같이 쓸 수 있다. 이렇게 쓰면 구체적으로 어떤 policy에 영향을 받지 않게 된다.
수식 3.16을 벨만 방정식 또는 Bellman optimality equation(벨만 최적 방정식)이라 부른다. 어떤 state의 optimal value function은 반드시 그 state가 가진 optiaml action의 expected return과 같다는 뜻이다. 그러니까 어떤 state s의 optimal value function은 그 state s에서 optimal policy에 따라 선택할 수 있는 action들 중 가장 높은 action value function과 같다고 해석할 수 있다.
그리고 optimal action value function으로 나타낸 벨만 최적 방정식은 아래와 같다.
밑의 백업다이어그램은 optimal value function과 optimal action value function의 벨만최적방정식의 next state와 action을 보여준 것이다. 에이전트가 action을 선택할 때 호가 추가되어 policy에 따라 최대값을 선택한다는 것만 빼면 위의 다이어그램과 동일하다.
이런 optimal value function \({v}_{*} \)가 있으면 optimal policy를 결정하기가 쉽다. 각 state에서 벨만 최적 방정식을 통해 얻을 수 있는 최대값을 주는 action은 여러개가 있을 수 있는데 이런 action들에 0이 아닌 확률을 할당해주는 것이 optiaml policy다. 만약 optimal value function \({v}_{*} \)를 가지고 있다면 현재 state에서 선택한 action은 optimal action일것이다(one-step search). 이말은 곧 optimal value function에서는 greedy policy가 optimal policy라는 뜻이다.
근데 \({q}_{*} \)를 알고 있으면 optimal aciton을 더 쉽게 선택할 수 있다. \({q}_{*} \)가 있으면 에이전트는 어떠한 state s에서든 \({q}_{*}\left(s, a \right) \)를 최대화할 수 있는 action을 쉽게 찾을 수 있게 된다. optimal action value function은 다음 state와 그 value가 뭔지 몰라도 optimal action을 선택할 수 있게 해준다. 즉 환경의 dynamics를 몰라도 optimal action을 선택할 수 있게 해주기 때문에 더 유용하다.
벨만 최적 방정식을 명확하게 해결하면 optimal policy를 찾는 경로를 알 수 있고 강화학습 문제를 풀 수 있다. 하지만 이 해결책은 거의 유용하지 않다. 왜냐하면 모든 가능성을 계속 찾고 그것들이 일어날 가능성과 expected reward를 모두 계산해야하기 때문이다. 이 해결책은 최소 3가지 가정에 의존한다. (1) 환경의 dynamics를 정확하게 알고 있다. (2) 이 문제의 해결법을 완전히 계산할 수 있을정도로 계산자원이 충분해야 한다. (3) Markov Property. 일반적으로 우리가 관심있는 종류의 task들은 (1), (2), (3)이 적절하게 조합되어 만족되지 않는다. 예를들으 TD-gammon의 경우 (1), (3)은 문제가 없는데 (2)의 경우가 문제다. \(10^{20} \)개의 state들을 가지고 있기 때문에 벨만방정식을 푸는데 매우 오랜시간이 걸린다. 그래서 강화학습에서는 일반적으로 근사시켜서 해결법을 찾아야한다.
Optimality and Approximation
우리는 앞에서 optimal value function과 optimal policy를 정의했다. 에이전트가 optimal policy를 잘 학습하는 것은 실제로 매우 드문일로, optimal policy는 오직 엄청난 계산을 통해서 얻어진다. 위에서 얘기한 것처럼 우리가 모델의 dynamics를 완벽하게 잘 알아도 벨만최적방정식을 풀어 optimal policy를 계산하는 것은 불가능하다. 에이전트가 마주보는 가장 중요한 측면은 주어진 계산량, 특히 action을 한번 선택할 때(한번의 time t에서) 에이전트가 계산할 수 있는 양이다.
가용할 수 있는 메모리의 양 또한 중요한 제약조건이다. 대용량의 메모리는 value function, policy, model들의 근사를 만들기 위해 필요하다. 작업량이 작고 유한한 state에서는 배열이나 테이블을 사용해 각 state를 근사할 수 있다. 이 방법을 tabular 방법이라 부른다. 하지만 실제로는 테이블로 표현할 수 있는 것보다 매우 많은 state가 존재한다. 이런 경우는 더 간결하게 파라미터화한 function들을 사용해 근사해야 한다.
강화학습에 대한 이런 틀은 우리가 근사치를 정하게 강요하지만, 우리에게 유용한 근사치를 달성할 수 있게 기회를 준다. 예를 들어 에이전트가 suboptimal action을 선택하는 것은 에이전트가 받는 reward에 거의 영향을 미치지 않을 낮을 확률로, 에이전트가 직면한 state가 많을 수도 있다.(For example, in approximating optimal behavior, there may be many states that the agent faces with such a low probability that selecting suboptimal actions for them has little impact on the amount of reward the agent receives, 영어가 좀 어렵다.) TD-gammon 플레이어의 경우 고수가 게임을 할경우 절대 일어나지 않을 상태같은 나쁜 결정을 내릴 수 있는데도 불구하고 특별한 스킬로 게임을 한다. 사실이 플레이어는 아주 다양한 게임의 상태에 대해 상당부분 나쁜 결정을 내릴 수도 있다.
online 강화학습의 특징은 자주 접하지 않는 state에 대해서는 노력을 줄이고 자주 접하는 state에 대해 더 좋은 결정을 내리기 위해 더 많이 노력하는 optimal policy를 근사할 수 있다. 이는 MDP를 해결하기 위한 다른 접근방법들과 강화학습을 구분해주는 중요한 특징이다.(내용도 좀 어렵다)
요약
이번챕터에서는 강화학습에 어떤 요소들이 있는지를 봤다. 강화학습은 goal을 달성하기 위해 환경과 어떻게 상호작용하며 행동해야하는지를 학습하는 것으로 환경과 에이전트는 discrete time step으로 서로 상호작용한다.
Action은 에이전트에 의한 선택이고, state는 이런 선택을 만들기 위한 기초이다. 그리고 reward는 이런 선택을 평가하기 위한 기초이다. policy는 state의 함수로서 에이전트가 action을 선택하는 stochastic rule이다. 에이전트의 목표는 장기적인 시점에서 에이전트가 받을 reward들을 최대화하는 것이다.
이런 강화학습의 요소는 transition probability인 MDP로 아주 잘 정의될 수 있다. finite MDP는 한정된 state, action, reward set을 지닌 MDP로 현재 강화학습의 많은 이론들은 finite MDP로 제한되어 있다.
또 return이라는 것이 있었다. return은 에이전트가 최대화하려고 하는 future reward의 함수이다. return은 discounting이 적용되지 않은 episodic task와 episode로 나눠지지 않고 무한히 지속되는 continuing task로 나눠진다. 우리는 이 두 종류의 task를 하나의 방정식을 이용해 정의하려고 했다.
그 다음으로 value function은 에이전트가 policy를 사용해 action을 선택할 경우 각 state 또는 state-action 쌍에 할당된다. optimal value function또한 각 state 또는 state-aciton 쌍에 할당되는데, 어떤 policy에서 달성가능한 가장 큰 expected return을 optimal value function이라고 부른다. 그리고 각 state또는 state-action마다 optiaml value function을 선택한다면 이게 바로 optimal policy다. 이런 optimal value function은 주어진 MDP에 의해 고유한 것이지만 다양한 optimal policy가 있을 수 있다. 그리고 optimal value function에 대해 greedy한 선택을 하는 모든 policy는 optimal policy다.
벨만최적방정식 또한 optiaml value function을 반드시 만족해야하며, 원칙적으로는 optimal value function에 대해 해결할 수 있는 특수한 조건이다.
강화학습 문제는 최초에 에이전트가 환경에 대해 알고 있는 정보에 따라 다르다. complete konwledge문제에서 에이전트는 완전하고 정확한 환경의 dynamics에 대한 모델을 가지고 있다. 만약 이 환경을 MDP로 정의한다면, 위에서 본 4개의 아규먼트를 가진 dynamics function p로 구성될 수 있다. 하지만 incomplete knowledge문제에서는, 완전하고 완벽한 환경의 모델은 불가능하다.
만약 에이전트가 완전하고 정확한 환경의 모델을 가지고 있다고 하더라도, 에이전트는 value function들을 구하기 위해 충분한 계산을 할 수 없다. 메모리 가용량 또한 중요한 제약조건이기 때문이다.
우리는 모든 종류의 강화학습 문제에 대해서 optimal한 해결책을 찾을 수 없지만, 어떠한 방법으로든 반드시 근사하는 방법에 대해 많은 관심이 있다.
Reference
'강화학습 > RL Introduction 책 요약' 카테고리의 다른 글
| Multi-armed Bandit(Chapter 2) (0) | 2020.05.20 |
|---|---|
| 강화학습이란 무엇인가(Chapter 1) (0) | 2020.05.17 |