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는 어디로 갈 지 모르는 상황, 액션을 하며 샘플!

카일스쿨 유튜브 채널을 만들었습니다. 데이터 분석, 커리어에 대한 내용을 공유드릴 예정입니다.

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

이 글이 도움이 되셨거나 의견이 있으시면 댓글 남겨주셔요.