Udacity Deep RL Nanodegree — Reinforcement Learning

커리큘럼1은 고전적인 강화학습 알고리즘에 대해서 다룬다. 내용들을 정말 간단하게만 정리했다.

Agent-Environment Interaction

  • agent와 environment가 상호작용하며 학습하는 것이 Reinforced Learning
  • Agent는 environment에 action을 주고 새로운 상태(state)와 보상(reward)를 받음. 한 번 action을 주고 state, reward를 받는 것을 timestep이라고 함.
  • Task: RL 문제를 나타냄.
  • Episodic Task: 시작과 끝이 명확히 존재하는 테스크, 종료지점에 도달하면 끝남. 한번 시작해서 종료지점까지 진행하는 것을 하나의 episode라고 함. 여러 episode를 경험하면서 학습함.
  • Continuing Task: 영원히 계속되는 테스크
  • Reward Hypothesis: 각 스탭에서의 보상 R(t)의 합을 최대화하도록 학습함.
  • Discounted Return: 미래의 얻을 수 있는 보상의 합(Gt)을 계산할 때, 더 이후의 timestep일 수록 가중치를 줘서 값을 줄임.

Markov Decision Process(MDP)

  • set of states S
  • set of actions A
  • S(t), A(t) = timestep t에서의 상태 S(t), 행동(A(t)
  • R(t) =state s에서 action a를 선택했을 때의 보상을 확률적으로 나타냄

Monte Carlo Methods

  • 각 state에서 어떤 action을 선택할지를 policy라고 함.
  • Monte Carlo는 무작위 action을 선택한 뒤, 그 reward를 저장함
  • 이를 수없이 반복하다보면, 대부분의 state, action에 대한 reward를 알 수 있음. 이를 저장하는 곳이 Q-Table, 이하 QT(state, action) = reward로 표시
  • 처음에 학습 단계에서는 무작위로 reward를 파악하고, 실제 test 단계에선 여태까지 학습한 Q Table을 이용해서 state에서 가장 좋은 reward를 주는 action을 가져옴
  • 하지만 state, action의 reward는 그때그때 다를 수 있음. 이 때 Q Table의 reward를 갱신하는 방법에는 크게 두가지가 있음
  • First-Visit MC: 처음 선택한 state, action의 reward를 저장하고 갱신하지 않음
  • Every-Visit MC: state, action의 reward들의 평균을 q-table에 저장

Greedy Policy

  • greedy policy는 Q Table의 state에서 가장 좋은 reward를 주는 action을 가져오는 정책임
  • epsilon-greedy policy는 (1-eplison) 의 확률로 greedy policy를 선택하고, 나머지 확률로 random policy를 선택하는 것.
  • 이를 통해 항상 최적의(greedy) action 을 선택하지 않고, 일정 확률로 모험을 하게됨(eplison : 0 ~ 1 사이의 실수)
  • 강화학습은 학습과정에서 모험을 할지(Exploration of uncharted territory) 아니면 현재의 지식을 개척할지(Exploitation of current knowledge) 이 epsilon 값을 통해서 조절할 수 있음.

Temporal Difference(TD)

  • 이전까지의 방법들은 한 번의 에피소드를 마친 후 새로 발견한 값들을 이용해 Q-Table을 갱신했음.
  • 이런 방식은 비효율적, 매 timestep마다 Q-Table을 갱신하면 더 빠르게 학습할 수 있음. 이것을 Temporal Difference라고 함.
  • on-policy: 경험한 내용을 바탕으로 policy를 예측, 개선
  • off-policy: 경험하지 않은 내용도 경험한 내용을 바탕으로 예측하고 개선해나감.
  • On-line Learning: 매 step에서 예측하고 받은 reward를 그대로 학습에 반영하는 방식
  • 크게 Sarsa, Sarsamax, Expected Sarsa가 있음

Sarsa or Sarsa(0)

  • 현재 state에서 policy(e-greedy 같은거)로 action을 선택함, 그러면 next_state를 알게 됨
  • next_state에서 policy로 next_action을 선택하고 Q Table에서 next_reward를 가져옴
  • reward와 Q-table에 있는 reward의 차이 계산 R(t+1) — Q(St, At)
  • 거기에 next_reward(= Q(St+1, At+1)) 에 gamma를 곱한 값을 더한 후
  • 그 값을 alpha만큼 곱한 후 Q Table에 더함
  • 이를 정리하면, 새로운 reward 값을 alpha만큼 Q Table에 반영하고, 새로운 reward에는 next_reward까지 gamma만큼 반영됐다는 것이다.
  • 이 때 alpha를 step size라고 함.
  • GLIE (Greedy in the Limit of Infinite Exploration): episode를 계속 진행하면서 점점 e-greedy를 greedy하게 만드는 것(epsilon 값을 줄이는 것). 예를 들어 epsilon = 1 / episode 을 해서 에피소드가 진행할 수록 epsilon을 줄이는 방법이 있다.

Sarsamax

sarsamax는 next_action을 고를 때 policy를 통해 고르는 게 아닌, Q Table의 next_state에 해당하는 reward 중에서 가장 높은 reward를 가진 action을 선택하고 next_reward를 받아오는 방법이다. Q-learning 이라고도 한다.

Expected Sarsa

Expected Sarsa 는 next_reward를 계산할 때, next_state의 모든 가능한 next_action의 reward와 그 next_action이 발생할 확률을 곱하고 그 합을 next_reward로 사용한다. 예를 들어 next_state의 action과 reward(Q-table에 있는 값), action을 고를 확률이 아래처럼 있다면

action | reward | prob |
0 | 10 | 0.5 |
1 | 15 | 0.4 |
2 | 20 | 0.1 |
next_reward = 10 * 0.5 + 15 * 0.4 + 20 * 0.1 = 13

next_reward는 13이 된다.

TD Control Method 정리

  • Sarsa(혹은 Sarsa(0)라고 함): 스텝크기 alpha가 충분히 작고, epsilon이 GLIE 조건을 만족할 때 최적의 Q값 수렴 보장. on-policy TD Control method
  • Sarsamax: off-policy TD Control. sarsa와 같은 조건하에 수렴 보장
  • Expected Sarsa: on-policy TD Control. sarsa와 같은 조건하에 수렴 보장

성능 분석

  • on-policy(Sarsa, Expected Sarsa)가 off-policy(Sarsamax)보다 온라인 성능이 좋음.
  • Expected Sarsa가 일반적으로 Sarsa보다 성능이 좋음.

Continous Spaces

이전까지의 학습은 state와 action의 값이 유한하고 이산적이었음. 하지만 예를 들어 state가 0~1사이의 무한한 값이라거나 하는 상황에서는 Q-Table을 만들 수 없음

Discretization

연속적인(Continous) 값을 이산적(Discretization)인 값으로 바꾸는 방법

  • Uniform Discretization: 0~1 사이의 값이라고 하면 동일한 간격으로 나눔. 예를 들면 0~0.2의 값을 0.1로 바꾸고, 0.2~0.4를 0.3으로 바꾸고, …
  • Non-Uniform Discretization: 동일하지 않은 간격으로 나눔. 예를 들면 0~0.4의 값을 0.2로 만들고, 0.4~0.5의 값을 0.45 로 바꾸는 등

이러 state의 범위를 유한하게 만들 수 있고 state-action Q Table을 만들 수 있다.

Tile Coding

값의 범위를 규칙적인 크기로 나뉜 Tile에 해당하는 값으로 바꿈.

예를 들어 0.4 라는 값은 0.3 ~ 0.7의 범위를 이산화한 tile에서는 0.5가 되고, 0.2~0.4의 범위를 이산화한 tile에서는 0.3이 된다. 서로 다른 종류의 타일마다 Q-Table을 만들고 최종 reward를 예측할 때는 모든 Q Table 값의 평균으로 사용한다.

Coarse Coding

기본적으로 tile coding과 비슷하지만 비규칙적으로 나뉜 영역으로 이산화함.

여기까지가 고전적인 강화학습 방법들

Function Approximation

연속적인 state문제를 근본적으로 해결하기 위해 선형 혹은 비선형 함수 f를 만들고 f(state, action) = reward를 맞추도록 한다. 이 과정에서 딥러닝의 gradient decent를 이용해서 최적의 값을 찾아가게 된다. 앞으로 커리큘럼 2부터는 이런 Deep Reinforced Learning에 대해서 다룰 것이고. 커리큘럼1에서는 고전적인 강화학습 알고리즘에 대해서 다뤘다.

Written by

2020.12.8 ~ 2022.6.9 군복무중 Serving in the South Korean Military Service

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store