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

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

Introduction

환경과 상호작용을 통해 학습하는 것은 아주 기본적인 아이디어다 의심의 여지 없이 우리의 삶에서 환경과 상호작용하며 학습하는 것은 환경과 우리 자신에 더 잘 알 수 있는 방법이다

이 책에서는 이러한 상호작용으로 목표에 달성하는 다양한 learning method들을 평가한다 reinforcement learning은 다른 어떠한 머신러닝 알고리즘보다 목표지향적인 알고리즘이라 할 수 있다

1.1 Reinforcement Learning

Reinforcement Learning은 reward signal을 최대화 시키면서 학습한다. 에이전트는 어떤 action을 해야하는지가 아니라 어떤 action을 해야 가장 많은 reward를 얻는지를 발견해야한다. 그리고 이 action은 눈앞의 reward뿐만 아니라 다음 상황, 그리고 더 먼 상황의 reward에까지 영향을 미친다. 이 두가지 특성-trial and error search와 delayed reward-가 reinforcement learning의 중요한 특징이다

 Reinforcement learning 문제는 dynamical systems theory를 사용해 정의한다. 구체적으로 Markov decision process이다

 Reinforcement learning은 지도 학습과 비지도 학습과는 다르다. 지도학습과 비지도학습은 머신러닝을 둘로 갈라 놓는 것 같지만 그렇지 않다. reinforcement learning은 머신러닝의 3번째 패러다임이다.

 Reinforcement learning에서는 다른 학습 알고리즘과 다르게 exploration과 exploitation이 트레이드오프 관계에 있다. 많은 reward를 얻기 위해 에이전트는 과거에 효과적으로 reward를 얻었던 action을 선호하는데 이러한 action을 선택하기 위해서 그전에 선택하지 않은 action을 선택해야 한다. 에이전트는 reward를 얻기 위해 이미 시도했던 action을 다시 선택하는 exploit과 미래에 더 좋은 reward를 받기 위한 action을 explore해야 한다. 이런 exploration-exploitation의 딜레마는 아직 풀리지 않은 숙제이다. 이런 exploration과 exploitation의 균형을 맞추는 문제도 지도, 비지도 학습에서는 드러나지 않는다.

 Reinforcement learning의 또 다른 특징은 목표지향적인 에이전트가 확실하지 않은 상황과 상호작용하는 것이다.

 모든 reinforcement learning 에이전트들은 명확한 목표가 있고 action을 선택해 환경에 영향을 미친다.

 현재의 reinforcement learning의 양상 중 가장 흥미로운 것은 다른 공학과 과학 분야와 상호작용있는 것이다. 일부 reinforcement learning 방법은 매개변수로 근사하는 것으로 고전적인 '차원의 저주'를 해결한다. reinforcement learning은 사람과 다른 동물들이 학습하는 방법과 유사하고 많은 reinforcement learning의 핵심 알고리즘은 생물학적인 학습 방법에서 영감을 받았다.

앞으로 전체적으로 배울 것들에 대한 소개

1.2 Examples

• 태어난지 얼마안된 어린 가젤은 걷기 위해 노력한다. 반 시간 후에는 20miles/hour로 달린다.

• 로봇청소기는 쓰레기가 남아있는 방에 들어가야하는지 배터리를 재충전하기 위해 돌아가는길을 찾아야하는지 결정해야한다. 로봇청소기는 배터리의 잔량과 과거에 얼마나 빠르게 쉽게 배터리 재충전기를 찾았는지를 고려해 결정한다.

• 기타 등등... 

 이러한 예제들은 간과하기 쉬운 기본적인 특징을 공유한다. 모든 예제는 적극적인 의사결정 에이전트와 환경이 상호작용한다. 에이전트들은 그 환경에 대해서 잘 모르지만 목표를 달성하기 위해 노력한다. 에이전트의 행동들은 미래의 환경의 상태에 영향을 미친다. 동시에 에이전트는 환경을 계속해서 모니터링하고 환경과 적절하게 상호작용해야한다. 위의 예제들은 에이전트가 정한 목표에 얼마나 도달했는지에 관한 진행도를 알 수 있다. 어린 가젤은 언제 넘어지는지를 알고 로봇청소기는 언제 배터리가 다 닳는지를 안다.

 이러한 모든 예제에서 에이전트는 시간이 경과할수록 본인의 경험을 이용해 성능을 증가시킬 수 있다.

강화학습의 에이전트는 환경과 적극적으로 상호작용함, 그리고 에이전트의 행동들은 환경에 영향을 미치기 때문에 에이전트는 계속해서 환경을 관찰하고 상호작용해야함

1.3 Elements of Reinforcement Learning

에이전트와 환경의 문제를 넘어 reinforcement learning 시스템에서는 4가지 요소가 있다. policy, reward signal, value function 그리고 model of environment(옵션).

 Policy는 어떤 시각에서 에이전트가 어떻게 행동해야하는 지를 학습하는 것이다. policy로 에이전트의 행동을 결정해서 policy는 reinforcement learning 에이전트의 핵심이라고 할 수 있다. 보통 policy는 확률적일 수 있고 각 action에 대한 확률들로 나타낼 수 있다.

 Reward signal은 reinforcement learning 문제의 목표이다. 각각의 time step에서 환경은 에이전트에게 reward라는 단일 숫자를 보낸다. 에이전트의 목표는 긴 시간동안 받을 reward의 총합을 최대화하는 것이다. reward signal은 policy를 바꿀수 있는 기본적인 특징이다. 만약 policy에 의해 선택된 action이 낮은 reward를 준다면 policy는 미래에는 이 action이 아닌 다른 action을 선택할 것이다. 보통 reward signal은 환경의 state와 어떤 action을 선택할 것인지에 대한 확률적인 함수이다.

 Rewrad signal이 눈 앞의 즉각적인 이득이라면 value function은 긴 시간동안의 이득이라고 할 수 있다. state의 value는 미래에 받을 수 있는 에이전트가 기대하는 reward의 총합이다. 예를 들어 어떤 state는 즉각적이지만 항상 낮은 reward를 주지만 그럼에도 불구하고 높은 value를 준다. 왜냐하면 이 state에 따라오는 다른 state들이 높은 reward를 주기 때문이다. 이 반대의 경우도 성립될 수 있다.

 Reward가 제일 중요하고 반면에 value는 reward의 예측값이므로 두번째로 중요하다. reward 없이는 value도 없다. value값을 평가하는 이유는 더 많은 reward를 얻기 위함으로 에이전트가 어떤 결정들이 좋은지 평가해야할 때는 value를 제일 많이 고려한다. action을 선택할 때 value를 고려하기 때문이다. 우리는 어떤 state에서 가장 높은 reward가 아니라 가장 높은 value를 주는 action을 찾는다. 왜냐하면 이런 action들은 미래에 우리에게 더 많은 reward를 줄 것이기 때문이다. reinforcement learning 알고리즘에서 가장 중요한 요소는 효과적으로 value를 측정하는 방법이다.

 4번째이자 마지막 요소는 model of environemt이다. state와 action이 주어지면 모델은 다음 state와 reward를 예상할 수 있다. 모델은 planning에 사용된다. planning이란 실제로 경험하기 전에 가능한 미래의 상황을 고려해 action을 결정할 수 있는 방법이다. reinforcement learning 문제를 푸는 방법 중에서 model과 palnning을 사용하는 방법을 model-based 방법이라 부른다. 이는 trial-and-error를 사용하는 model-free 방법과는 반대된다.

policy : 에이전트가 어떤 action을 할 확률
reward signal : 강화학습 문제의 목표가 되는 것. 또한 에이전트의 목표는 미래에 받을 reward의 총합을 최대화하는 것
value function : 에이전트가 기대하는 reward의 총합, reward가 눈앞의 이득이라면 value function은 멀리보고 기대되는 이득
에이전트가 action을 선택할 때 value를  고려해 선택, 강화학습 아고리즘에서 제일 중요한 것은 효과적으로 value를 측정하는 방법을 찾는 것
model of environment : 환경의 모델을 이용해 에이전트가 행동하지 않고 state와 reward를 예상할 수 있음. 모델과 planning을 이용하는 방법이 model-based방법

1.4 Limitations and Scope

강화학습의 핵심 컨셉은 state다. state는 policy와 value function의 입력으로 사용되고 모델에서는 입력과 출력 둘 다에 사용된다. state는 에이전트가 환경에서 이용가능한 정보로 볼 수 있다.

 이 책에서 고려할 대부분의 강화학습 방법들은 value function을 추정하는 법들이다. 하지만 강화학습 문제들을 푸는데 value function이 필수적인 것은 아니다. 예를 들어 유전 알고리즘은 value function을 추정해 최적화하는 방법을 사용하지 않는다.

state는 강화학습의 핵심 컨셉, 에이전트가 환경에서 이용가능한 정보.

1.5 An Extended Example: Tic-Tac-Toe

간단한 예제로 강화학습에 대해 공부, 이러한 전통적인 sequential decision 문제의 최적화 방법은 dynamic programming이 있다.

틱-택-토 게임

틱택토 - 나무위키

 틱택토 게임을 어떻게 value function을 이용한 방법으로 풀수가 있을까. 첫번째로 게임의 가능한 상태들에 대해서 숫자 테이블을 설정한다. 상태에서 각 숫자들은 게임에서 이길 수 있는 확률을 추정한 것이다. 이러한 추정치를 state의 value로 한다. state A가 state B보다 더 높은 value를 가지고 있으면 A가 B보다 이길 수 있는 확률이 더 높다.

 X로 플레이한다고 가정했을 때, 1번의 경우 모든 state에서 이길 확률은 1이되고(이미 이겼기 때문에), 2번의 경우 모든 state에서 이길 확률은 0이된다(이미 졌기 때문에). 마지막으로 3번의 경우 아직 게임을 시작하지 않은 상태로 모든 state에서 이길확률은 0.5다.

 게임을 하면서 우리는 현재 value 테이블을 참고해 아직 돌이 놓이지 않은 비어있는 공간에 돌을 둘 수 있다. 대부분의 시간에 우리는 가장 높은 승리확률을 추정한 값인 가장 높은 value값을 greedily 선택 한다. 경우에 따라서는 아예 무작위로 선택을 할 수 있는데 이 방법을 exploratory라고 부른다

 우리가 플레이하는 동안 state의 value를 우리가 찾은 값으로 바꾼다. 이 게임에서 승리할 확률을 더 정확하게 추정하게 위해 "back up" 방법을 사용한다. 각각의 greedy 선택 후의 state value를 선택하기 전의 상태로 back up 한다. 더 정확하게 말하자면 이전 state의 value를 나중 state의 value에 가깝게 업데이트한다. \( {S}_{t} \)는 greedy 선택을 하기 전의 state이고 \( {S}_{t+1} \)은 선택한 후의 state이다.

그리고 업데이트된 \( {S}_{t} \)의 추정 value를 \( V\left({S}_{t} \right) \)로 쓸 수 있으며 다음 수식과 같이 표현한다.

$$ V\left({S}_{t} \right) \leftarrow V\left({S}_{t} \right) + \alpha\left[V\left({S}_{t+1} \right) - V\left({S}_{t} \right) \right] $$

 \( \alpha \)는 학습률에 영향을 주는 스텝사이즈 파라미터이다. 이 업데이트 방법은 temporal-difference 학습 방법의 예이다. 이렇게 부르는 이유는 연속적인 시간에서 \( V\left({S}_{t+1} \right) - V\left({S}_{t} \right) \), 이 차이를 기본으로 식을 업데이트하기 때문이다.

 위의 temporal-difference식은 스텝사이즈 파라미터가 시간에 따라 적절하게 감소하고 플레이어가 optimal 플레이를 하면 각 state에서 승리할 수 있는 참 확률로 수렴한다. 이 방법은 optimal policy로 수렴하게 된다.

 플레이어는 탐험으로 여러가지를 선택할 수 있고 이중에 하나를 선택한다. 플레이어의 두번째 선택인 e는 가장 높은 값을 주지 않지만 탐험으로 선택한 행동이다. 그래서 위의 value function 업데이트식을 사용해서 state를 업데이트하지 않는다. 그 외의 나머지 플레이어의 선택은 가장 높은 값을 주는 선택이므로 가치함수 업데이트 식을 사용해 이전 state를 나중 state값을 이용해 업데이트 시킨다

 틱택토 예제는 evolutionary 방법과 value function을 사용하는 방법의 차이를 설명해준다. evolutionary 방법에서는 각 policy들의 변화는 많은 게임들을 플레이한 후 그 결과만을 이용한다. 즉 게임을 하는 동안 일어났던 일들에 대해서는 무시해버린다. value function 방법은 그와 대조적으로 각각의 state들을 평가한다. 

틱택토게임을 학습시키기위해 value function을 사용했음, 여기서 value는 승리할 수 있는 확률. 테이블의 각 칸을 하나의 state라고 두고 이 state의 value를 학습시켜서 승리할 수 있는 최적의 value를 찾아냄
그리고 최적의 value를 찾아내기 위해 업데이트 하는 식 소개

1.6 Summary

강화학습은 목표지향학습과 의사결정을 이해하고 자동화하는 computational approach다. 에이전트가 환경과 직접적으로 상호작용하며 학습하는 것을 강조한다. 강화학습은 Markov decision processes를 사용해 학습하는 에이전트와 환경(states, actions, rewards) 사이의 상호작용을 정의한다. 이런 framework(MDP)는 인공지능 문제에서 필수적인 특징들을 간단한 방법으로 표현하려고 한다. 이러한 특징들에는 원인과 결과 불확실성과 비결정론(?), 명백한 목표의 존재 등이 있다.

 Value와 value function의 컨셉은 대다수의 강화학습 방법들의 키다. value function들은 효과적으로 policy를 찾는데 중요하다. value function을 사용하는 것은 전체 policy들의 evaluation에 따라 policy들을 직접적으로 탐색하는 evolutionary 방법과 강화학습을 구분한다.

1.7 Early History of Reinforcement Learning

강화학습 역사설명?

 

Reference : Reinforcement Learning : An Introduction