Reinforcement Learning 책 읽고 공부하기(3)

sutton 교수의 Reinforcement Learning An Introduction을 읽고 공부하기

Chapter 3

Finite Markov Decision Processes

이번 챕터에서는  finite Markov decision processes(finite MDPs)의 문제를 소개한다. 이 문제는 bandit문제와 마찬가지로 evaluative feedback을 포함할 뿐만 아니라 associative aspect(다른 상황에서는 다른 action들을 선택) 또한 포함한다. MDPs는 연속적인 decision making을 공식화한 것이다. 연속적인 decision making이란 지금 선택한 action이 즉각적인 reward뿐만 아니라 그 후에 상황, state, 미래의 reward에 까지 영향을 미침을 의미한다. 따라서 MDPs는 즉각적인 reward와 나중에 받을 reward 사이에 균형을 맞춰야 한다.

  MDPs는 강화학습문제에서 수학적으로 이상적인 형태이다. 이 문제에서의 핵심적인 요소들로는 returns, value functions, Bellman equations 같은 것이 있다. 유한 MDP로 공식화할 수 있는 예제를 볼 것이다. 모든 인공지능 문제들은 적용범위와 수학적으로 다룰만한 것들 사이에 간격이 있다. 이 챕터에서는 이런 간격을 소개하고 tradeoff를 본다.

MDP에 들어가기 앞서 MDP란 무엇인가!
MDP는 연속적인 decision making을 공식화 한것으로 현재 선택한 actoin이 미래의 state, reward에 까지 영향을 미침

3.1 The Agent-Environment Interface

MDP는 목표를 달성하기 위해 상호작용을 통해 배우는 문제를 하나의 프레임처럼 만든 것이다. learner와 decision maker를 이제부터 에이전트(agent)라고 부르고 에이전트 밖에서 에이전트와 상호작용하는 것들은 환경(environment)라 부른다.  이 상호작용은 에이전트가 actions을 선택하면 환경이 action에 대한 상황(situation)을 에이전트에게 알려주면서 계속해서 진행된다. 환경은 또한 reward를 에이전트에게 주고 에이전트는 action을 선택하며 이 reward가 최대가 되는 법을 찾는다.

그림 3.1: Markov decision processes에서 에이전트-환경 상호작용

  더 정확하게는  에이전트와 환경은 이산 타임스텝 \(t \)마다, \( t=0,1,2,3,... \) 환경의 state를 받고 그걸 기반으로 action을 선택한다. 하나의 타임스텝이 지나면 에이전트는 숫자로 된 reward를 받고 새로운 state를 찾는다. MDP와 에이전트의 상호작용의 순서는 다음과 같이 나타낼 수 있다.

$$ {S}_{0}, {A}_{0}, {R}_{1}, {S}_{1}, {A}_{1}, {R}_{2}, {S}_{2}, {A}_{2}, {R}_{3}, ... $$

  유한 MDP문제에서 states, actions, reward들의 집합(\( S, A, R \))은 모두 유한 집합이다. 이 경우 \( {R}_{t}, {S}_{t} \)는 이전 state, action과 연관된 이산 확률 분포다. 그러므로 \( s', r \)은 이전 시각 t-1에서 state와 action이 주어졌을 때  다음 시각 t에서

\( s', r \)이 나올 확률이다.

$$ p\left( s', r | s,a \right) \doteq Pr \left\{ {S}_{t}=s', {R}_{t}=r | {S}_{t-1}=s, {A}_{t-1}=a \right\} $$

함수 p를 MDP의 dynamics라 정의한다. dynamic function \(p : S \times R \times S \times A \rightarrow \left[0,1 \right] \)는 4개의 아규먼트에 대한 일반적인 deterministic 함수이다. 가운데의 '|'는 조건부확률을 나타낸다. 아래와 같은 표현은 \( p \)가 s, a에 대한 확률분포임을 보여준다.

$$ \sum_{s' \in S }^{} \sum_{r \in R}^{} p\left( s',r | s,a \right) =1, \textrm{for all} \,\, s \in S, a \in A \left( s\right) $$

  \( {S}_{t}  \)와 \( {R}_{t} \)의 가능한 value의 확률은 오직 바로 직전 state와 action인 \( {S}_{t-1} \), {A}_{t-1}에 의해서만 결정된다는 것을 보여준다.  이는 decision process가 아닌 state가 제한사항임을 알 수 있다. 에이전트-환경의 상호작용에서 나중에 차이를 만들 수 있는 정보를 state가 가지고 있다면  state를 Markov property라고 부를 수 있다.

  4개의 아규먼트를 가지는 dynamic function \(p\)에서 state-trainsition 확률이라는 환경에 대한 다른 정보를 계산할 수 있다. 이는 3개의 아규먼트만 사용해서 표현한다. \(p: S \times S \times A \rightarrow \left[ 0,1 \right] \)

$$ p\left( s'|s, a \right) \doteq Pr \left\{ {S}_{t} =s' | {S}_{t-1}=s, {A}_{t-1}=a \right\} = \sum_{r \in R}^{} p \left( s', r | s,a \right) $$

또한 두개의 아규먼트를 사용함으로써 state-action쌍의 reward 기대값을 계산할 수 있다. function \( r : S \times A \rightarrow R \)(실수)

$$ r(s,a) \doteq E\left[ {R}_{t} | {S}_{t-1} =s, {A}_{t-1} = a \right] = \sum_{r \in R}^{}r \, \sum_{s' \in S}^{} p \left( s', r| s,a \right) $$

그리고 세개의 아규먼트를 사용해서 state-action-nextstate의 reward 기대값을 계산할 수 있다. \( r : S \times A \times S \rightarrow R \)(실수)

$$ r\left( s,a,s' \right) \doteq E\left[ {R}_{t}| {S}_{t-1}=s, {A}_{t-1}=a, {S}_{t}=s' \right] = \sum_{r \in R}^{} r \frac{ p\left( s', r | s, a\right)  }{ p \left( s' | s,a \right) } $$

책에서는 4개의 아규먼트를 사용하는 표기법을 쓴다.

  MDP 프레임워크는 추상적이고 유연해 다른 여러 문제들에 여러 방법으로 응용될 수 있다. 비슷하게 state도 여러 다양한 형태가 존재한다. action도 비슷하다. 보통 action은 어떠한 결정이 될 수 있다.

  에이전트와 환경 사이의 경계는 로봇이나 동물의 몸과같은 전형적인 물리적 경계가 아니다. 예를 들어 로봇과 모터의 기계적인 연결과 하드웨어 산서는 에이전트가 아니라 환경의 부분으로 고려해야한다. 이와 비슷하게 MDP 프레임워크를 사람 또는 동물에게 적용하려면 근육, 뼈, 센서 기관들은 환경의 일부로 생각해야한다. reward 또한 자연 및 인공적인 학습 시스템의 내부에서 계산되지만 에이전트의 밖에 있는 것으로 간주한다.

  일반적인 규칙은 에이전트가 임의로 바꿀 수 없는 것은 환경의 일부로 생각하는 것이다. 우리는 환경의 모든 것을 에이전트가 모른다고 가정하진 않는다. 예를 들어 에이전트는 reward가 어떻게 state와 action의 함수로 계산되는지 안다. 하지만 항상 reward의 계산은 에이전트의 밖에 있다. 왜냐하면 에이전트는 이를 임의로 바꿀 수 없기 때문이다. 사실 어떤 경우에 에이전트는 환경이 어떻게 동작하는지 모든 것을 알지만 여전히 어려운 강화학습 문제가 존재한다. 루빅스 큐브의 경우 어떻게 동작하는지 정확히 알지만, 여전히 풀지는 못한다. 에이전트-환경의 경계는 에이전트의 지식이 아닌 에이전트의 절대적인 제어(absolute control)의 제한이 나타낸다.

  에이전트-환경의 경계는 다른 목적으로 다른 장소에 위치한다. 복잡한 로봇에서 다양한 많은 에이전트들이 각각의 고유한 경계로 작동한다. 실제로 에이전트-환경의 경계는 특정 state, action, reward를 선택하면 결정된다.

  MDP 프레임워크는 상호작용으로부터 배우는 목표 지향적인 문제의 상당한 추상화다.  MDP는 센서, 메모리, 제어 장치등이 달성하려는 목표가 무엇이던지 목표지향적 행동의 문제는 에이전트와 환경 사이의 세가지 신호로 줄일 수 있다고 제안한다. 하나의 신호는 에이전트에 의해 선택되는 것(actions), 다른 신호는 이 action을 기반으로 만든 신호(states), 다른 하나는 에이전트의 목표(rewards). MDP 프레임워크는 모든 decision-learning 문제들에 충분히 유용하진 않지만 유연하고 유용하다는 건 증명됐다.

  당연하게도 state와 action은 작업마다 상당히 다르고 어떻게 표현하느냐가 성능에 상당한 영향이 있다. 이 책에서는 state와 action을 어떻게 잘 선택하느냐에 대해 조언과 예제를 알려준다.

환경-에이전트의 상호작용을 MDP를 통해 표현. MDP를 통해 강화학습의 여러가지 문제를 풀 수 있음
MDP를 이용해 환경-에이전트의 state, action, reward를 표현하고 이 세가지를 통해 환경-에이전트 사이의 경계를 나눔. 그래서 state와 action을 어떻게 선택하느냐가 중요한 문제임

 

Example 3.1: Bioreactor

Example 3.2: Pick-and-Place Robot 반복적인 pick-and-place를 하는 로봇 팔의 움직임을 학습시키는데 강화학습을 적용해본다고 생각해보자. 학습하는 에이전트는 빠르고 부드럽게 움직이기 위해 현재 위치와 속도의 정보를 가지고 모터를 직접적으로 제어하는 것을 학습한다 이 경우 action은 각 관절에 있는 모터에 적용하는 전압, state는 가장 최근에 읽은 관절의 각도와 속도. reward는 물체를 성공적으로 집고 내려놨을 경우 +1이 된다. 부드러운 움직임과 빠르게 옮기기 위해 negative reward(벌점)는 모션이 제대로 이어지지 않는 경우라고 할 수 있다.

Example 3.3: Recycling Robot

3.3은 좀 길다. 사무실 환경에서 빈 캔을 정리하는 일을하는 청소로봇이 있다치자. 캔을 탐지하고 로봇팔로 줏어서 onbard bin에 넣는다. 로봇은 배터리로 움직인다. 캔을 탐지하는 high-level decision은 현재 배터리량을 기반으로 한 강화학습 문제로 푼다. 배터리 잔량에 관한 state는 S = {high, low}로 표현한다. 각 state마다 에이전트가 할 수 있는 행동들이 있다. (1) 일정 시간동안 캔을 탐색, (2) 누군가 캔을 가져올때까지 가만히 기다림, (3) 집으로 돌아가 배터리 재충전. 그래서 할 수 있는 action의 집합들을 다음과 같이 표현한다. A(high) = {search, wait}, A(low) = {search, wait, recharge}.

  대부분의 시간동안 reward는 0이다. 로봇이 빈 캔을 확보한다면 +가 될 것이고 배터리가 모두 소진되면 -를 reward로 받는다. 로봇이 search할때 배터리는 닳는다. 배터리량이 high일 경우 search를 해도 배터리가 모두 소진될 위험은 없다. high로 시작했을 때 high로 search가 끝날 확률은 \( \alpha \)이고 low로 끝날 확률은 1-\( \alpha \)로 한다. low로 시작했을 때 low로 끝날 확률은 \( \beta \)이고, 배터리가 모두 소질될 확률은 1-\( \beta \)로 한다. 배터리가 모두 소진된 경우 로봇은 구출되야 한다. 이러나저라나 reward가 -3이라면 로봇은 구출되야 한다.

  \( r_{search} \), \( r_{wait} \), \( r_{search} > r_{wait} \)으로 serarch와 wait에서 로봇이 수집할거라 기대하는 캔의 양(expected reward)을 표시한다. 이 시스템은 유한 MDP이고 transition probability와 expected reward 그리고 dynamics로 왼쪽 테이블과 같이 나타낼 수 있다.

테이블의 행은 현재 state와 다음 state의 가능한 조합이다. 어떤 transition들은 일어날 가능성이 없어 expected reward가 없다. 오른쪽은 유한 MDO의 dynamics를 나타내는 또 다른 유용한 방법으로 transition graph라 부른다. 여기에는 state와 action node 두가지가 존재한다. 

  start node s에서 시작해 action node a를 지나가면 (s, a)가 된다. 각 화살표는 (s, s', a)에 대응하고 s'은 next state다. 그리고 각 화살표의 transition probability는 p(s'|s, a)이고 이에 따라오는 expected reward는 r(s,a,s')이다. action node를 떠나는 화살표의 transition probability의 합은 항상 1이다.

환경-에이전트를 MDP를 사용해 나타낸 예제

 

 

 

Reference : Reinforcement Learning : An Introduction