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


카일스쿨 유튜브 채널을 만들었습니다. 데이터 분석, 커리어에 대한 내용을 공유드릴 예정입니다.

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

이 글이 도움이 되셨거나 의견이 있으시면 댓글 남겨주셔요.

Buy me a coffeeBuy me a coffee



© 2017. by Seongyun Byeon

Powered by zzsza