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

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

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

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

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

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

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

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