Reinforcement Learning 2강. MDP

in Data on Reinforcement-Learning


  • David Silver의 Reinforcement Learning 강의를 한국어로 해설해주는 팡요랩 영상을 보고 메모한 자료입니다

2강. Markov Decision Process

  • MDP
  • 강화학습이 적용되는 도메인이 다 MDP
  • MDP에서 최적의 Sequential한 Decision Making을 어떻게 풀어나갈 것이냐? ← 강화학습이 풀고자 하는 문제
  • MDP가 무엇인지, 어떤 용어와 개념이 있는지 차근차근 배울 예정
  • 이전 history를 버리고 state만 기억하면 될 경우 markov property
  • Markov Process
  • Markov Reward Processes
  • Markov Decision Processes
  • 순으로 진행하고
  • Extensions to mdps는 실버 강의에서 다루지 않아서 패스!

Introduction to MDPs

  • Markov decision process는 RL에서 환경을 표현
    • Environment는 모두 관측가능한 상황!
    • 즉, 현재 state가 프로세스의 특징을 완전히 나타냄
  • 대부분의 RL 문제는 MDP 형태로 만들 수 있음
    • Optimal control 문제를 continuous MDP로 다루고
    • Bandit 문제도 1 state를 가진 MDP

Markov Property

  • The future is independent of the past given the present
  • \[P[S_{t+1}|S_{t}] = P[S_{t+1}|S_{1}, ..., S_{t}]\]
  • State가 모든 관련된 정보를 가지고 있어서 state만 필요할 뿐
  • The state is a sufficient statistic of the future

State Transition Matrix

  • Environment를 설명할 때 필요하는 것들
  • 시간 t일때 s에 있고 액션이 없음. 다음 스텝으로 옮길 때 (t+1) 여러 액션으로 전이할 확률
    • s에서 s 프라임으로 갈 확률

Markov Process(or Markov Chain)

  • 상태들이 N개 있음
    • discrete하게 뚝뚝 끊어지며 state를 움직임
    • 계속 옮겨다님
  • memoryless random process
    • memoryless : 내가 어느 경로로 왔는지 상관 없이 이 곳에 도착하는 순간 미래가 정의
    • random process : 샘플링을 할 수 있음
  • S, P로 정의됨
    • S는 유한한 state들의 세트
    • P는 state transition probability matrix
    • 어떤 조건을 만족하면 최종 분포가 stationary가 됨
      • 1억명을 state에 두고 계속 전이하면.. staet마다 있는 수가 일정하게 됨
  • Student Markov Chain
    • 에피소드를 샘플링한다는 표현을 쓸 예정
    • 샘플링을 한 것은 확률 변수가 있고 이벤트가 발생(시뮬레이션)
    • 여기서 Transition Matrix로 표현하면

Markov Reward Process

  • Markov Process는 S, P만 있었는데 이젠 R, gamma가 추가됨
  • R은 reward funtion, 어떤 state에 도달하면 reward를 몇을 줘라! 이런 것을 정의
    • n개 있으면 됨
  • gamma : discount factor, 0~1
  • state에만 reward를 줌
  • 예시

Return

  • 강화학습은 Return을 maximize!
    • Reward랑 다름
    • Return은 total discounted reward from time step t
    • 감가상각 개념! 미래..
    • 감마가 0에 가까울수록 근시안(myopic), 1에 가까우면 큰 그림(far-sighted)
  • Discount를 꼭 해야 해?
    • 솔직한 이유는 수학적으로 편리해서
      • Discount때문에 수렴성이 증명! 수렴해야 크고 작음을 표시할 수 있음
    • 동물과 사람의 행동이 즉각적 리워드를 선호함
    • 만약 모든 시퀀스가 종료되는 것이 보장되면 감마를 1로 해도 될 수 있음
    • 문제에 따라 discount가 필요한 문제, 안 필요한 문제가 있음

Value Function(MRP)

  • Return의 기대값!
  • MRP에서 Value Function은 state에 왔을 때, 그 state에서 계속 샘플링하며 에피소드를 만들어감
    • 에피소드마다 Return이 생김
    • 샘플링에 따라 return이 달라짐
    • return의 평균
    • State S에 왔을 때 G의 기대값(어느 정도의 return을 받을지 예측할 수 있음)
      • return을 \(G_{t}\)로 표현, 확률 변수

Bellman Equation for MRPs

  • 정말 중요! Value based method에선 엄청 나옴
  • value funtion이 학습되는 것은 모두 벨만 방정식에 근거해서 학습
  • 벨만 방정식
    • 감마로 묶어! \(G_{t+1}\)이 v
    • 점화식처럼 표현!
    • S에서 value는 한 스텝을 가고 + 다음 스테이트에서 value에 감마를 곱한 것
  • 매트릭스 형태로 표현하면
  • 식을 정리하면 \(v = (1 - \gamma P)^{-1}R\)
    • r, P, 감마가 주어지면 v를 구할 수 있음
    • 계산 복잡도는 \(O(n^{3})\)라서 비싼 연산
    • Direct solution은 오직 작은 MRP에서만 가능
    • 큰 MRP의 경우 다른 방법
      • Dynamic programming
      • Monte-Carlo evaluation
      • Temporal Difference learning

Markov Decision Process

  • MDP는 MRP에서 A(Action)이 추가됨
  • A : action들의 집합
    • action마다 reward가 주어짐
    • action을 하면 확률적으로 state로 가게 됨(그림에선 pub)
  • state에 있으면 확률분포에 의해 넘겨줬는데, 이번엔 정책에 따라 액션이 달라짐
  • Policies
    • Plicy is a distribution over actions given states
    • \[\pi (a|s) = P[A_{t}=a|S_{t}=s]\]
    • S_{t}에 있을 때 a를 할 확률
    • Agent의 행동을 정의해줌
    • 현재 state만 있으면 됨(history 필요 없음)

Value Function

  • 아깐 파이가 없었음
    • 이젠 파이가 있어야 함
  • 어떤 스테이트에서 폴리피 파이를 끝까지 했을 때, 에피소드가 1개 나옴 ⇒ 여러개를 계속 뽑아서 샘플링 ⇒ 평균이 Value Function
  • State Value Function
    • input이 state 하나만 들어갈 경우
  • Action Value Function
    • input이 state, action이 들어갈 경우
    • \[q_{\pi}(s,a) = E_{\pi}[G_{t}|S_{t}=s, A_{t}=a]\]
    • 큐함수
    • 큐러닝, DQN 모두 이걸 학습!

Bellman Expectation Equation

    • s에서 a를 했을 떄, 파이를 따라서 게임을 끝까지 하면 얻을 return의 기대값
      • 어떤 state에 떨어질지 모름. 모든 state에 갈 수 있음
      • 각 state에 떨어질 확률가 그 state에서 value를 곱하고 더함
      • 감마는 discount
  • action을 어떻게 해야되는진 아직 배우지 않음

Optimal Value Function

  • Optimal state-value function
    • 파이가 아닌 star로 표현
    • 어떤 policy를 따르든(세상에 다양한 policy.. 무한의 value..) 그 중 제일 나은 것
  • Optimal action-value function
    • 할 수 있는 모든 policy를 따른 q 함수 중에 max
  • optimal value function을 아는 순간 MDP는 풀렸다(Solved)라고 함

Optimal Policy

  • 두 폴리시가 있을 때 하나가 나은지 비교
  • partial ordering
    • 어떤 두개에 대해 이게 더 낫다고 존재한다고 할 수 있음
  • q star를 알고 그걸 따라가면 optimal policy다
  • MDP에선 deterministic optimal policy가 존재
    • deterministic! 가위바위보에 해당 ⇒ 무조건 가위만

Solving the Bellman Optimality Equation

  • non-linear라서 closed form이 없음
  • 많은 반복적 솔루션이 존재
    • Value Iteration
    • Policy Iteration
    • Q-learning
    • Sarsa

Reference


카일스쿨 유튜브 채널을 만들었습니다. 데이터 사이언스, 성장, 리더십, BigQuery 등을 이야기할 예정이니, 관심 있으시면 구독 부탁드립니다 :)

PM을 위한 데이터 리터러시 강의를 만들었습니다. 문제 정의, 지표, 실험 설계, 문화 만들기, 로그 설계, 회고 등을 담은 강의입니다

이 글이 도움이 되셨거나 다양한 의견이 있다면 댓글 부탁드립니다 :)

Buy me a coffeeBuy me a coffee



© 2017. by Seongyun Byeon

Powered by zzsza