[ 강화학습 ] 3. Finite Markov Decision Processes
이 책의 남은 파트에서 지속적으로 다룰 문제를 소개하는 중요한 챕터로 이 문제를 해결하는 방법을 우리는 강화학습이라 여긴다. 이번 챕터를 통해 강화학습 문제가 어떤 것인지 개괄적으로 알아보고 그 응용에 대해 다룬다. 또한 강화학습 문제의 수학적으로 이상적인 형태를 다루고 Bellman equation이나 Value function과 같이 강화학습 문제의 수학적 구조의 중요한 요소들에 대해 학습한다.
3.1. The Agent-Environment Interface
앞서 계속 언급하였듯 강화학습에서 agent는 actions를 선택하고 environment는 그 actions에 반응하여 agent에게 새로운 situation을 제시하며, reward를 발생시킨다. 그리고 agent는 시간을 거쳐 그 reward를 maximize하려고 노력한다. 각 time step에서 agent는 state로부터 각 action을 선택하는 가능성을 mapping하는데 이를 agent의 policy라 부르며 pi_t로 표기한다. pi_t(aㅣs)는 state가 s일 때 action이 a일 확률을 뜻한다. 강화학습은 어떻게 agent가 experience의 결과로 그 policy를 바꾸는 지를 규명하는 것이다. 책에는 여러가지 예시가 나와있지만 이해를 위해 한 가지만 가져왔다.
Example 3.3 : Recycling Robot
빈 음료 캔을 사무실이라는 environment에서 모으는 것이 로봇의 업무라 하자. 로봇은 센서와 gripper 그리고 충전이 가능한 배터리로 구성된다. 로봇은 sensory information을 해석하는 파트, navigating 파트, arm과 gripper를 조종하는 파트로 이루어지며 빈 캔을 어떻게 찾는지에 관한 High-level decision이 배터리 충전 정도에 따른 강화학습으로 가능해진다. agent는 (1) 로봇이 캔을 찾아다닐지, (2) 누군가 캔을 가져다주는 것을 기다리며 정지해있을지, (3) 배터리를 충전하러 충전소로 돌아갈지를 결정해야하며 이러한 결정들은 매 시간 이루어진다. 이러한 예시에서 강화학습의 agent는 로봇 자체가 아니다. 로봇이 관찰하는 state는 로봇 내에 condition을 묘사하는 것이지, 로봇의 외부 환경의 condition을 묘사하는 것이 아니며 agent의 environment가 로봇의 외부 환경과 로봇의 나머지 부분을 포함한다.
3.2. Goals and Rewards
강화학습에서 agent의 목표는 당장의 reward를 최대화하는 것이 아닌 cumulative reward를 최대화하는 것이다. 전진하는 로봇을 예로 생각해보자. 각 시점에서 로봇의 forward motion에 비례하여 reward를 제공한다. 미로를 탈출하는 로봇을 생각해보자. 시간이 지날 때마다 -1의 reward를 주었더니 결과적으로 로봇의 미로 탈출 속도는 빨라졌다. 이 섹션에서 워낙 강조하는 내용이라 원문 그대로 가져오면 다음과 같다.
The reward signal is your way of communicating to the robot what you want it to achieve,
not how you want it achieved.
체스에서 승리하는 로봇을 학습시키고 싶은데 이기는 행위에 reward를 주지 않고 승리하기 위한 행위 즉, 상대의 말을 잡는 행위에 reward를 주게 되면 로봇은 체스 승리가 아닌 상대방 말을 무조건적으로 잡는 것을 목표로 하여 승리할 가능성은 적어지게 된다.
3.3. Returns
앞에서 강화학습의 개념을 추상적으로 알아봤다. 이제 그 과정을 어떻게 수식으로 정의할 수 있을지에 대한 이야기다. 만약 각 time step에서 받는 일련의 reward가 R_t1, R_t2, R_t3, ... , 라고 표기된다면 우리가 maximize하고 싶은 expected return인 G_t는 다음과 같이 표기될 것이다.
G_t = R_t1 + R_t2 + R_t3 + R_t3 + ... + R_t
t = final time step
하지만 이러한 표기법은 final time step이 존재한다는 가정에서만 유효하다. 책에서 episode라 표현하는 agent-environment interaction은 terminal state라 불리우는 special state가 존재하고 starting state라는 초기상태로 reset되어 episode는 다시 시작된다. 이러한 episode로 구성된 task를 episodic task라 하며 terminal state의 유무에 따라 아래와 같이 나뉜다.
𝒮 : set of all nonterminal states
𝒮+ : set of all states plus terminal state
반면에 대부분의 agent-environment interaction의 경우 식별 가능한 몇몇 episode로 구분되는 것이 아니라 계속적으로 이어지는 경우가 있다. 이를 continuing tasks라 정의한다. 위에서 정의한 expected return은 continuing tasks에서는 final time step이 t가 아닌 무한대이기에 그 계산이 불가능함을 쉽게 알 수 있다. 때문에 이 책에서는 return의 정의를 개념적으로는 조금 더 복잡하게 그러나 수식으로는 보다 간단하게 설명한 정의를 이용한다.
continuing task에 해당하는 return의 수식적인 정의를 위해 우리는 discounting이라는 개념을 추가적으로 활용한다. 마찬가지로 긴 시간에 거쳐 축적된 reward를 maximize하는 방식이지만 expected discounted return을 최대화한다는 점에서 차이가 있다.
r는 0과 1사이의 값을 가지는 parameter로 discount rate라 불린다.
r이 1에 가까울수록 미래의 reward에 가중치를 부여하고
r이 0에 가까울수록 미래의 reward에 가중치를 줄이는 역할을 한다.
즉, discount rate는 future rewards의 현재 가치를 결정한다.
r이 0이라고 생각하면 agent는 당장의 reward만 고려해서 이번 action을 결정한다고 생각하면
직관적으로 이해할 수 있겠다. 반대로 1에 가까우면 future reward를 고려하는
more farsighted(멀리 내다보는) agent가 되시겠다 ~
3.4. Unified Notation for Episodic and Continuing Tasks
크게 중요한 섹션은 아니고 앞에서 정의한 Episodic Task랑 Continuing Task를 둘 다 계속 다룰텐데 헷갈리면 안되니까 Notation을 명확히 하자!! 라는 취지의 섹션인 것 같다. 결론은 둘을 분리시키자가 아니다. 통합된 Notation을 사용할 수 있다는 것이니 헷갈리지 말자. 간단히 생각해보면 Continuing Task가 expected reward 나타낼 때도 좀 더 복잡했으니 Notation도 복잡하지 않을까 생각할 수 있지만 반대다. Episodic Task의 경우 Episode가 하나일 수도 있고 연속적인 Episode가 존재할 경우도 있기 때문이다. 하지만 본 저서에서는 대부분 episode를 구분할 필요가 없기에 time step과 episode를 둘 다 표시할 필요는 없다고 한다. 또, reward가 1, 1, 1, 0, 0, 0, 0, ... 인 Continuing Task 역시 episode의 종료 시점만 명확히 하면 그 Notation이 통합될 수 있다. 그 표기는 아래와 같다.
* 3.5. The Markov Property
섹션 앞에 * 가 붙는다. 이번 섹션에서는 environment의 특징을 정의하고, environment의 state signal의 특징인 Markov property에 대해 공부한다. 우리가 중점적으로 공부할 내용은 environment로부터 나오는 state signal이 어떻게 구축되고, 바뀌는 지가 아니라 state signal에 따라 달라지는 action에 관한 것임을 기억하자. 이상적으로는 state signal이 past sensation에 대한 정보를 compactly 가지고 있는 것이다. 이처럼 모든 관련 정보를 보유하는데 성공한 state signal을 우리는 Markov라 부르거나 Markov Property를 지녔다고 표현한다. 모든 관련 정보를 보유하였다는 것에 과거의 즉, information about the sequence까지 보유하였다고 생각하면 오산이다. future flight를 위해 필요한 것은 현재 cannonball의 위치와 속도이지, 어디서 왔는지가 아니다. 이를 independence of path 라고도 표현한다. path는 history라고 받아들여도 좋다.
이를 수식으로 표현하기 위해 state와 reward value의 수가 finite 하다고 가정하자. 인테그랄이나 확률 분포보다는 합과 확률 자체가 더 계산하기 편리하니.
딱 봐도 3.5가 간단하다. 이것이 Markov property 유무의 차이다. Markov property를 지닌 state signal에서 t+1 시점에 environment's response는 오직 t 시점의 state and action representations에 좌우된다. 그 외 시점의 state와 action은 신경쓰지 않아도 좋다는 의미다. Markov Property를 지닌 environment가 실생활이나 강화학습에서 지배적이진 않지만 Markov state라는 가정하에 짜여진 알고리즘이 실생활에 잘 적용되고 있다는 점에서 그 의미가 있다.
3.6. Markov Decision Processes
해당 섹션의 첫 문장이 다음과 같다.
A reinforcement learning task that satisfies the Markov property is called a Markov decision precess, or MDP
여기에 state와 action space가 finite하면 finite Markov decision process라고 불린다. 이 Finite MDP를 우리는 남은 챕터들에서도 지속적으로 다룰 것이면 현대 강화학습의 90%를 이해하는데 필요한 것이 바로 Finite MDP라며 저자는 방점을 둔다. Finite MDP의 이해를 위해 앞서 예로 들었던 청소 로봇을 다시 꺼내보자.
청소 로봇은 매 시점 (1) 캔 찾아다니기, (2) 누군가 가져다주길 기다리기, (3) 배터리 충전하러 가기 중에 한 가지를 결정한다. 캔을 찾는 최선의 방법은 (1) 이지만 배터리가 소모되고 배터리가 다 소모되면 누군가 충전기로 옮길 때까지 기다려야한다. 당연히 이는 low reward를 만든다. agent는 배터리 수치만을 고려하여 결정을 내린다. 이 때, state set은 S = {high, low}, 가능한 결정은 wait, search, recharge.
A(high) = {search, wait}
A(low) = {search, wait. recharge}
캔을 하나 찾을 때마다 reward가 1씩 늘어나고 rescue 될 때마다 -3의 reward를 획득한다.
transition graph를 통해 finite MDP의 dynamics를 정리해보자.
3.7. Value Functions
모든 강화학습 알고리즘은 state 혹은 state-action pairs에 대한 함수인 value function에 대한 평가를 포함한다. 이는 주어진 state에서 agent가 어떻게 있었는지에 대한 평가 척도이다. 얼마나 잘 있었냐에 대한 것은 future reward의 관점에서 바라볼 수 있으며 value functions은 특정 policies에 관해 정의된다. policy는 문자 𝝅로 표시되며 각 state와 action으로부터 state s 일 때 action a를 취할 확률 𝝅(aㅣs)로의 mapping이다.
< state-value function for policy 𝝅 >
Informally, the value of a state s under a policy 𝝅, denoted v_𝝅(s)
expected return when starting in s and following 𝝅 thereafter
< action-value function for policy 𝝅 >
유사하게 value of taking action a in state s under a policy 𝝅, denoted q_𝝅(s, a) 는
expected return starting from s, taking the action a, and thereafter following policy 𝝅
value function인 v_𝝅 와 q_𝝅 는 경험으로부터 측정된다. 즉, agent가 policy 𝝅를 따라 각 state에서 평균을 구한다면 이는 state-value function v_𝝅(s)에 수렴할 것이다. 실제 returns의 많은 랜덤 샘플의 평균을 구하는 방법이 Monte Carlo Methods로 추후 챕터에서 다룰 것이다.
Reinforcement Learning과 Dynamic Programming에서 사용될 value function의 근본적인 성질은 value function이 recursive relationship을 가지고 있다는 것이다. 임의의 policy 𝝅 와 state s에 대하여 다음 조건을 충족시킨다.
위 식은 v_𝝅 에 대한 Bellman Equation이다. 이는 state value와 successor states의 values 사이의 관계를 보여준다.
하얀 원은 state, 검은 점은 action이다. Bellman Equation은 발생할 가능성을 weight 삼아 구한 모든 가능성들의 평균이다. 그림 (a)를 예로 들면 agent가 오른쪽 action a를 결정하고 environment는 reward r과 state s'를 제공한다. 위와 같은 그림을 backup diagram이라 하며 강화학습에서 중요한 update 연산과 backup 연산을 개략적으로 보여준다.
3.8. Optimal Value Functions
Optimal Policy란 다른 모든 policy보다 그 value function의 값이 높은 policy다. 그 표기는 𝝅_* 다. optimal policies는 같은 state-value function을 가지며 이를 optimal state-value function이라 부르고 v_*라 표기한다.
또한 optimal policies는 같은 optimal action-value function인 q_*를 가진다.
state-action pair (s,a)에 관하여 위 함수는 action a를 state s에서 취하여 optimal policy를 따랐을 때 expected return을 의미하므로 다음과 같은 식으로 나타낼 수 있다.
즉, Optimal policy를 따른 state value function의 값과 해당 state에서 좋은 action을 선택하여 얻은 expected return이 같음을 의미한다. 앞에서 봤던 backup diagram으로 이해해보자.
앞서 봤던 diagram과의 차이점은 어떤 policy 환경에서 expected value를 통해 결정하는 것이 아니라 max choice를 고른다는 것이다.
finite MDPs 에서는 Bellman optimality equation의 unique solution이 policy와 관계없이 존재한다.
많은 decision-making methods가 Bellman optimality equation을 근사하여 푸는 방법으로 보여진다. 추후 배울 Dynamic Programming 역시 이와 관련되어 있다.
3.9. Optimality and Approximation
앞서 optimal value functions와 optimal policies를 정의했다. optimal policy를 학습한 agent는 매우 작동을 잘하겠지만 실제 그 application에 있어 optimal policies를 구해내는 것은 매우 높은 computational cost를 가진다. 따라서 대개 Bellman optimality equation을 풀어 optimal policy를 구하는 것은 불가능하다. 이에 앞 section에서 다룬 Approximation이 요구된다.
