5. 벨먼 방정식: 가치를 한 스텝씩 쪼개면 되풀이가 답에 모인다
자주 하는 실수와 요약
자주 하는 실수
| 실수 | 나온 문제 | 바로잡는 법 |
|---|---|---|
| 가치를 몇 달치만 더하고 끊음 | 1 | 「다음 상태의 앞으로의 값」이 그 상태의 가치임을 써서 식으로 접는다 |
| 퇴근도 할인도 없을 때 같은 방법으로 풀린다고 봄 | 2 | 행 합이 1이면 |
| 숫자들이 「비슷하다」로 벨먼 기대 방정식을 지킨다고 봄 | 3 | 확률 가중 평균을 셈해 견준다. 어긋나면 어느 숫자가 틀렸는지는 이 방정식만으로 모른다 |
| 길을 모두 늘어놓아 최단을 찾으려 함 | 4 | 갈림목마다 「여기서부터의 최선」 하나만 적고 뒤에서부터 셈한다 |
| 첫 결정이 같으면 가치도 같다고 봄 | 5 | 최적성의 원리: 첫 결정 뒤의 모든 상태에서 남은 결정이 다시 최적이어야 한다 |
| 지금 정책의 행동 가치를 |
6 | |
| 처음에 앞선 쪽은 계속 앞선다고 봄 | 7 | 배율이 1보다 작은 되풀이는 처음 차이를 배율의 거듭제곱으로 줄인다 |
| 8 | 퇴근 확률이 다음 구역 가치에 곱하는 수를 1보다 작게 만들어 할인율 노릇을 한다 | |
| 확률로 평균 내기만 해도 차이가 0으로 간다고 봄 | 8 | 모든 칸에 같은 수를 더한 차이는 줄지 않는다. 1보다 작은 배율이 있어야 한다 |
| 9 | 반드시 끝나는 에피소드에서는 끝의 값이 한 스텝에 한 칸씩 올라와 길이만큼이면 정확해진다 | |
| 오늘 보상이 큰 쪽으로 정책을 고침 | 10, 11 | 행동 가치 |
| 행동 가치가 같을 때도 바꿈 | 11 | 같으면 지금 행동을 둔다. 그래야 정책 반복이 멈춘다 |
| 거친 평가로 고쳐도 정책이 늘 나아진다고 봄 | 12 | 정책 개선 정리는 정확한 평가를 가정한다. 행동 가치 차이가 작으면 평가를 그만큼 정밀하게 해야 한다 |
요약
상태의 가치는 「이번 스텝의 보상 + 할인한 다음 상태 가치의 평균」으로 쪼개진다. 정책 하나에 대해 적은 관계가 벨먼 기대 방정식
정책 대신 행동 가운데 가장 큰 것을 고르면 벨먼 최적 방정식
벨먼 최적 방정식은 max 때문에 역행렬로 풀 수 없지만, 오른쪽을 되풀이해 적용하는 가치 반복으로 푼다. 벨먼 연산자
정책 반복은 지금 정책을 벨먼 기대 방정식으로 평가하고, 행동 가치가 큰 쪽으로 고치기를 되풀이한다. 정책 개선 정리가 고칠 때마다 가치가 줄지 않음을 보장하고, 택시에서는 평가 세 번에 최적 정책에 닿는다. 시어스 카탈로그를 되풀이로 풀던 하워드가 정책 반복을 찾았다. 평가 한 번은 가치 반복 한 스텝보다 비싸고, 평가가 거칠면 고치기가 엉뚱한 쪽으로 갈 수 있다.
막힌 곳
이 장의 셈은 모두 구역마다, 행동마다 다음 구역의 확률