Chapter 3. Dynamic programming

Presentation on theme: "Chapter 3. Dynamic programming"— Presentation transcript:

1 Chapter 3. Dynamic programming
Policy Iteration(벨만 기대 방정식) Value Iteration(벨만 최적 방정식) Ho-Bin Choi 순차적 행동 문제를 푸는 다이내믹 프로그래밍의 기본적인 아이디어는 큰 문제 안에 작은 문제들이 중첩된 경우에 전체 큰 문제를 작은 문제로 쪼개서 푸는 것입니다. 이때 각각의 작은 문제들이 별개가 아니기 때문에 작은 문제들의 해답을 서로서로 이용할 수 있는 특성을 이용하면 결과적으로 계산량을 줄일 수 있습니다. 다이내믹 프로그래밍에는 Policy Iteration과 Value Iteration이 있는데 Policy Iteration은 벨만 기대 방정식을 이용해 순차적 행동 결정 문제를 풀고 Value Iteration은 벨만 최적 방정식을 이용해 순차적 행동 결정 문제를 풉니다. Dynamic programming

2 Environment Environment.py 그리드월드 예제의 화면을 구성하고 실태,보상 등을 포함한 환경에 대한 정보를 제공하기 위한 함수로 구성되어 있다. Dynamic programming

3 ■그리드월드에서 에이전트가 알고 있는 환경의 정보
Environment ■그리드월드에서 에이전트가 알고 있는 환경의 정보 Dynamic programming

4 Iteration Policy_iteration.py PolicyIteration 클래스를 포함하며, 클래스에는 정책이터레이션의 알고리즘 관련 함수와 main 함수가 정의되어 있다. Value_iteration.py ValueIteration 클래스를 포함하며, 클래스에는 가치이터레이션의 알고리즘 관련 함수와 main 함수가 정의되어 있다. Dynamic programming

5 Policy_improvement()
Policy Iteration 모든 상태에 대해 벨만 기대 방정식을 계산하여 모든 상태의 가치함수를 업데이트 Policy_evaluation() 새로운 가치함수를 통해 탐욕 정책 발전으로 정책을 업데이트(정책 출력) Policy_improvement() 정책 평가와 정책 발전을 통해 얻은 정책에 따라 에이전트를 움직임 get_action(state) 모든 변수 초기화 Dynamic programming

6 Policy Iteration Value Iteration 명시적인 정책이 있음
정책을 평가(evaluation)하는 도구로서 가치함수를 사용 정책과 가치함수는 명확히 분리되어 있음 확률적인(stochastic) 정책(기댓값) → 벨만 기대 방정식을 사용 가치함수를 현재 정책에 대한 가치함수라고 가정 Value Iteration 정책이 명시적으로 표현되지 않음 정책의 발전(Improvement) 없이 가치함수를 업데이트 정책이 가치함수 안에 내재적(implicit)으로 포함되어 있음 결정적인(deterministic) 정책(틀린 가정) → 벨만 최적 방정식을 사용 가치함수를 최적 정책에 대한 가치함수라고 가정 → 정책 발전 필요 X Dynamic programming

7 Value Iteration value_iteration() get_action(state) get_action(state)
모든 상태에 대해 벨만 최적 방정식을 계산하여 모든 상태의 가치함수를 업데이트 value_iteration() 현재 가치함수를 바탕으로 최적 행동을 반환(정책 출력) get_action(state) 최적 정책에 따라 에이전트를 움직임 get_action(state) 모든 변수 초기화 Dynamic programming

8 환경을 모르지만 환경과의 상호작용을 통해 경험을 바탕으로 모델 없이 학습
다이내믹 프로그래밍의 한계 계산 복잡도 – 상태 크기의 3제곱에 비례 ex) 경우의 수가 우주의 원자 수보다 많은 바둑 Curse of Dimentionality(차원의 저주) 상태의 차원이 늘어나면 상태의 수가 지수적으로 증가 환경에 대한 완벽한 정보가 필요 보통 보상과 상태 변환 확률은 정확히 알 수 없음 현실 세계의 환경에 놓인 문제를 풀어내는 데는 위의 세 가지 한계가 치명적으로 작용합니다. 이러한 한계를 극복하기 위해서는 근본적으로 문제에 대한 접근 방식이 달라야 합니다. 환경을 모르지만 환경과의 상호작용을 통해 경험을 바탕으로 모델 없이 학습 강화 학습 Dynamic programming