Reinforcement Learning 3강. Planning by Dynamic Programming

Dynamic Programming

복잡한 문제를 푸는 방법
- 큰 문제를 작은 문제로 나누고 작은 문제에 대해 솔루션을 찾고 다 모아서 큰 문제를 품
강화 학습
- Model Free : environment가 어떤 것을 던져줄지 모를 경우(완전한 정보가 없을 경우)
- Model based : environment에 대한 모델이 있는 경우
  - 이 문제를 해결할 때 Planning, dynamic programming이 쓰임
Dynamic Programming의 조건
- 1) Optimal substructure
  - 작은 문제로 나뉠 수 있어야 함
- 2) Overlapping subproblems
  - 한 서브 문제를 풀고 나온 솔루션을 저장해(cached) 다시 사용할 수 있음
- MDP는 이 조건을 만족함
  - Bellman 방정식이 recursive
  - value function이 작은 문제들의 해

DP는 MDP에 대해 모두 알고 있다고 가정함
- State transaction, reward, …
2가지 문제가 있음
1) For prediction
- value function을 학습하는 것
- MDP가 있고 policy가 있을 때 그 policy를 따를 경우의 value function
- poliy evaluation
2) For control
- optimal policy를 찾는 것
- MDP만 있고 optimal policy를 찾음
- policy iteration, value iteration

이 policy를 따라갔을 때, return을 얼마 받는가?
- policy를 평가함 즉, value function을 찾는 문제
- Bellman expectation backup을 사용해서 계속 적용
- backup
  - 메모리에 저장
  - synchronous backup
예시
- MDP가 있고 policy가 있을 떄 value를 찾는 prediction 문제
- 주어진 바보같은 policy를 평가만 했을 뿐인데 평가된 value에서 greedy하게 움직이면 optimal policy가 찾을 수 있음
- 모든 문제에서 이게 됨! 신기
- 무한하게 갈 필요가 없음! 평가하게 greedy하게 움직이는 것을 만들자

Evaluate the policy(value function을 찾고)
Improve the policy by acting reddily(value function에 대해 greedy하게 움직이는 새로운 policy를 만들면)
이 Evaluate, Improve를 반복하면 converge됨
예제
- Jack’s Car Rental
- 좋은 문제인진 모름..
- 최대 20곳의 차가 있을 수 있음
- A는 포아송 분포로 차가 옴
- A에서 B로 B에서 A로 자꾸 차를 옮겨야 함
- 하나 빌릴때 10달러
- policy를 추측할 수 있음
- b는 수요가 더 많음
- a에서 차가 적어도 어쩔 경우엔 b로 옮기는 것이 나을 수 있음
- x축 : b 지점에 있는 차의 수, y축 : a 지점에 있는 차의 수
- iteration하면 수렴한다! 정도의 감만 잡으면 ok
증명
- 무조건 이전 policy보다 좋은가?
- 수렴 포인트는 optimal
Modified Policy Iteration
- 꼭 수렴할 때까지 해야되는가? 일찍 끝내면 안되는가
- k번만 하고 evaluation, improve해도 되지 않는가?
- 이렇게 해도 합리적임!

Principle of Optimality
Deterministic Value Iteration
- 서브 프러블럼의 솔루션을 알면 Bellman Optimality Equation을 이용해 s에서의 솔루션을 구할 수 있음
- 바로 이전 점에서 목적지까지 최단 거리를 구함. 그 전에서 구함.. 반복
value만 가지고 놈(value만 이터레이티브하게 update)
- policy 없음
예시
- 한 스텝들은 bellman optimality equation을 이용해 품
- 끝이란 것을 알 수 없어서 모두 다 돌아야 함

여태 나온 DP 방법들은 모든 stete들이 parallel되게 하는 synchronous backup을 사용했음
어떤 state만 하거나 순서를 다르게 하는 asynchronous한 방법을 이용하면 computation을 줄일 수 있음
모든 state가 골고루 뽑히면 수렴
방법론
- In-place dynamic programming
  - 코딩 테크닉
  - state가 n개 있으면 table이 있어야 함
    - 이전 step의 테이블 정보와 새로운 table
  - inplace는 하나만 가지고 있음!
- Proritised sweeping
  - 순서를 중요한 친구 먼저!
  - 중요한 정의 : bellman error가 큰 것
- Real-time dynamic programming
  - state space가 넓고 agent가 가는 곳은 한정적일 경우 agent를 움직이게 하고 정해진 곳을 방문하면 update
Full-width Backups
- DP는 full-width backup을 사용
- 큰 문제에선 DP를 사용할 수 없음(차원의 저주..)
Sample Backups
- state가 많아도 고정된 cost로 할 수 있음
- model free에서도 할 수 있음
  - 오늘은 model based를 생각했었음.
  - model free는 어디로 갈 지 모르는 상황, 액션을 하며 샘플!

카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)