Planning by Dynamic Programming

- Policy Evaluation - 정책이 정해졌을때(고정), Value Function이 어떻게 될지 찾는 것
- Policy Iteration - 최적의 정책을 찾아나가는 과정, 정책 중심
- Value Iteration - 최적의 정책을 찾아나가는 과정, 밸류 중심

 다이나믹 프로그래밍이란? 복잡한 문제를 푸는 방법론이다. 큰 문제를 작은 문제로 분할해서 풀고, 그 솔류션들을 저장해서 모아서 큰 문제를 해결

 

1. 큰 문제가 작은 문제로 나뉘어졌을때 답이 나와야 한다.
2. 작은 문제들을 저장해 둬서 사용이 가능해야 한다.
3. 마크로브 결정 과정이 동적 프로그래밍과 유사하다.

 

- 다이나믹 프로그래밍은 MDP에 대한 모든 지식을 알고 있다고 가정한다.
- prediction 문제는 value function을 찾는 것, control은 최적의 정책을 찾는 것 (목차에서 2번이 prediction, 3, 4번이 control)

 

- 어떤 정책을 평가하는 문제이다. 이 정책을 따라갔을때 리턴을 얼마나 받느냐(value function)를 찾는 것
- 백업(=메모리에 저장)

 

- 새로 업데이트한 정책이 이전 정책보다 더 좋은가를 증명하는 것. 더 좋다.
- 어떤 상태에 가면 무조건 특정 액션을 한다.
- q에 대하여 greedily 하게 움직임으로써 정책을 향상시킬 수 있다.

 

- Synchronous - 한타이밍에 모든 스테이트들을 전부 업데이트 하는 것
- Prediction 문제 - 벨만 중요, 정책 찾는 것
- Control - 가치 함수 찾는 것

 

- DP 방법은 synchronous(동기적) backups 방법이다.
- 모든 저장된 상태들은 평행하다.
- 비동기적으로도 할 수 있다. 각 상태들이 골고루 뽑힌다면, 유용하다

 

-   In-Place 방식은, 우리가 직접 만들어보면, 테이블이 2개가 필요하다.(이전 테이블에서의 상태 값, 우리가 새로 만들 테이블) In-Place 방식에선 테이블이 하나만 있어도 된다. 테이블 첫번째 값을 업데이트하고, 이전 데이터 값이 아닌, 첫번째로 업데이트 된 값을 바탕으로 두번째, 세번째 ... 값을 업데이트 해도 된다는게 증명되어 있다.

 

- 순서의 우선순위를 줘서 벨만의 에러가 가장 큰 값부터 업데이트 

 

- 에이전트를 계속 움직이게 하면서 에이전트가 방문한 테이블의 상태값만 먼저 업데이트

 

- 모든 DP 는 full-width backups 이다. 비싸다. Model-based 이다.

 

- 싸고 좋은 Sample Backups. 내 모델을 몰라도 할 수 있다.(Model-free)