[인공지능] Chapter 10. Markov Decision Process (2)

The Bellman Equations

• Bellman Equations
  • 지금 상태 s에서 이후 모든 상태 s’로 이어지는 값 중, 최댓값을 고르는 식
  • 최적화 문제를 푸는 데 사용
  • 순차적인 의사결정 문제를 다루는 데 활용
• How to be optimal
  1. Take correct first action
  2. Keep being optimal
• 벨만 방정식에서 agent가 얻을 수 있는 utility의 최적화된 값 (벨만 방정식의 두 가지 형태)
  • V*(s) (상태 가치 함수)
    • agent가 상태 s에서 시작
    • optimal 하게 행동한다면 행동 가능한 타임 스탬프 동안 얻을 수 있는 utility 기대값
  • Q*(s, a) (행동 가치 함수)
    • agent가 상태 s에서 시작
    • 행동 a를 시작한뒤 optimal하게 해동한다면 이후 얻을 수 있는 utility 기대값

Value Iteration

• V_k(s)
  • k번 행동할 수 있을 때 상태 s에서 시작해서 얻을 수 있는 최적화된 값
  • 타임 스탬프를 통해 k를 통해 utility를 확인한다는 점에서 마르코프 결정 과정은 주어진 k번 만에 종료됨
  • 아무런 행동도 하지 않은 상태에서는 얻은 보상이 없고, 다음 타임 스탬프 k+1을 살펴볼 때에는 Q*(s, a)를 최대화하는 값을 택해야 한다.
• Problems with Value Iteration
  • Value iteration repeats the Bellman updates

    

  • problem1
    • It’s slow per iteration
  • problem 2
    • The ‘max’ at each state rarely changes
  • problem 3
    • The policy often converges long before the values

 

 

Policy Extraction

• MDP의 가장 큰 목적은 MDPs를 푸는 최적화된 정책 π* 을 구하는 것
• 정책 추출을 통해 얻어낸 정책 π가 과연 모든 상태에서 optimal한 값을 얻을 수 있는 방법인지 확인
• Policy extraction
  • 강화학습에서 주어진 환경에서 학습한 정책을 실제로 실행 가능한 형태로 변환하는 프로세스
• Computing Actions from Values
  • We need to do a mini-expectimax

  

• Computing Actions from Q-Values
  • Completely trivial to decide

    

  
  
  • actions are easier to select from q-values than values

 

Fixed Policies

• Fixed Policy
  • 강화학습에서 사용되는 정책 중 하나
  • Expectimax trees max over all actions to compute the optimal values
  • If we fixed some policy, then the tree would be simpler (only one actions per state)
• Utilities for a Fixed policy
  • 고정된 policy 하에서 상태 s의 utility 계산
  • 예를 들어, 새로운 강화학습 알고리즘을 개발할 때, 이 알고리즘이 얼마나 효과적인지를 측정하기 위해 사용. 학습 중인 정책과 비교하여 얼마나 성능이 향상되는지를 측정하면서 알고리즘의 효과를 평가할 수 있음

Policy Evaluation

• Policy Evaluation
  • 강화학습에서 주어진 policy가 얼마나 좋은지 측정하는 과정
  • 어떤 상태에서 얼마나 좋은 행동을 취하는지 평가 → 이를 토대로 agent의 행동을 개선
  • 벨만 방정식을 통해 가치 함수를 반복적으로 업데이트하여 수행

Policy Iteration

• Policy Iteration
  • Step 1: Policy Evaluation
    • 고정된 policy의 utility 계산 (not optimal utility) (수렴할 때까지)
  • Step 2: Policy improvement
    • 수렴된 utility를 미래값으로 사용하여 One-step look-ahead 방식으로 정책을 업데이트
  • policy가 수렴할 때까지 반복
• Policy iteration
  • it’s still optimal
  • Can converge faster under some conditions
• 정리
  • Evaluation
    • Fixed current policy의 경우 정책 평가를 통해 값을 찾음
    • 값이 수렴할 때까지 반복
  • Improvement
    • 고정된 값의 경우, policy extraction을 통해 더 나은 정책 얻기
    • One-step look-ahead

Comparison

• 공통점
  • compute the same thing (all optimal values)
  • 둘 다 MDP를 해결하기 위한 동적 프로그램
• Value Iteration
  • 모든 iteration은 value와 policy를 업데이트함
  • policy를 추적하진 않지만, 최대값을 초과하는 작업을 수행하면 암시적으로 정책을 다시 계산
• Policy Iteration
  • fixed policy 로 utility를 업데이트하는 패스를 여러 번 수행
  • 정책이 평가된 후 새 정책이 수행
  • new policy가 더 좋음

Summary

• 최적의 값(optimal value) 계산
  • Value iteration 또는 Policy iteration 사용
• 특정 정책에 대한 값(value for a particular policy) 계산
  • Policy Evaluation
• Value를 policy로 전환
  • Policy Extraction
• 기본적으로 모두 Bellman updates의 변형
• 모두 one-step look-ahead 예상 조각을 사용
• 고정 정책을 연경할지 아니면 최대 오버 액션을 연결할지 여부만 다름