강화학습의 수학적 기초와 알고리듬 이해 - Week4

Smiling Sammy·2022년 1월 14일
0

고려대학교 산업공학과 정태수 교수님 강의 정리

Week4: 마르코브 과정

4-1. 마르코브 프로세스 개요

불확실성 모델링

  • Markov decision process
    • 확률적 동적 계획법: 동적 계획법 + 마르코브 프로세스
  • 확률 (Probability)
    • 주위에서 발생하는 여러 사건들 --> 근본적으로 불확실성 내포
    • 불확실성을 표현할 수 있는 수단
  • 확률변수와 확률분포
    • 예시 (날씨 - 맑음, 흐림, 비)
      • X=1(맑음 0.6), 2(흐림, 0.2), 3(비, 0.2)
      • P(X=1)=0.6, P(X=2)=0.2, P(X=3)=0.2
      • 확률변수(X) 정의 후 다양한 분석
    • 시간에 따른 날씨의 시계열
      • 불확실성, 내일 날씨와 오늘 날씨의 상관 관계가 존재함
        --> 시간의 흐름에 따라 불확실성 변동
      • 맑음 > 흐림 > 흐림 > 비 > 비 > 맑음 ...., 맑음 > 맑음 > 흐림 > 비 > 맑음 ....
        --> 확률에 대한 수학적 모델링을 위한 확률 프로세스

시간에 따라 확률적으로 변화하는 프로세스 예시

전염병 분석

  • 최근: ML등 데이터 기반 분석
  • 예전: 수학적 모델링 접근

사스 주차 별 신규 확진자 수

  • 신규 확진자가 시간의 흐름에 따라 변동
  • 공통 패턴: 일정 부분 증가 후 감소
  • 수학적 모델링을 통해 알고 싶은 점
    • 현재까지의 확진자 수 이력을 바탕으로 다음주에 추가 신규 확진자가 50건 이상 될 확률은?
    • 평균적으로 몇 주 후에 확산세가 진정될 것으로 예상되는가?

주가 분석

  • 시시각각으로 변하는 주가
  • 수학적 모델링을 통해 알고 싶은점: 주가가 패턴을 보이며 변동될 때, 주식은 어떻게 될까?

확률과정(Stochastic Process)

  • 개념
    • 확률적으로 변화하는 프로세스를 모델링하기 위해 수학적으로 접근하는 방법
    • Random process, Stochastic process
  • 정의
    • 불확실성을 가지고 변하는 일련의 과정
    • 시간에 따라 어떤 사건이 발생할 확률 값이 변화하는 과정
    • 시간이 진행함에 따라 상태가 확률적으로 변화하는 과정
  • 정리
    • 불확실한 시스템 모델링: 확률과 확률변수
    • 각각의 어떤 시점을 하나의 확률변수로 정함
    • 시간에 따른 확률변수들의 집합 {Xt:tT}\{X_t: t \in T\}
    • 확률변수와 결합확률분포 정의 필요

추가 용어

  • 시간공간(Time space)
    • 시스템의 상태를 관찰하는 시점들의 집합
  • 상태와 상태공간
    • 상태(State): 확률변수들이 가지는 어떤 값 (시스템의 상태)
      • 예시: 주가, 날씨, 전염병 신규 확진자 수
    • 상태공간(State space): 확률과정 Xt:tT{X_t:t \in T}의 확률 변수 XtX_t가 가질 수 있는 모든 가능한 값들의 집합

확률과정 예시 - 동전던지기

  • 게임 개요
    • 동전 하나를 던져서 앞면이 나오면 +1점, 뒷면 나오면 -1점
    • 기존 점수에 더한 것이 동전던지기 게임의 점수
    • 플레이어가 종료를 선언한 시점에서 게임 종료
    • 마지막 점수가 양수면 점수 당 천원 + 음수면 점수 당 천원 -
    • 점수는 0점부터 시작
  • 확률과정
    • 확률 변수 XnX_n: n번째 동전을 던졌을 때까지의 누적점수
    • 상태공간 S={,2,1,0,1,2,\cdots, -2, -1, 0, 1, 2, \cdots}
    • 시간공간 T={0,1,2, ....}
  • 게임 과정
    • 앞면이 나오면 +1, 뒷면이 나오면 -1
    • 시간의 흐름에 따라 불확실성을 가지고 변동되는 프로세스

확률과정 4가지 분류


예측

  • 확률과정을 통해 알고 싶은 것 --> 예측
  • 확률과정 {Xt:tTX_t: t \in T}에 대해: P(Xk+1Xk,Xk1,..,X0)P(X_{k+1}|X_k,X_{k-1}, .., X_0)?
    • 확률과정이 정의되기 위해서는 결합확률분포가 정의되어 있어야됨
    • 결합확률분포는 아래와 같이 조건부 확률의 곱으로 표현됨
    • 즉, 조건부확률은 확률과정의 결합확률분포를 결정하는 중요개념

Episode

  • 확률과정의 실현된 값들의 sequence (= sample path)
  • 확률과정의 실현치들을 모아놓은 것 (일종의 시계열 데이터 샘플)

정상과정(Stationary process)

  • 시간 t에 따라 확률법칙이 변하지 않는 확률과정
  • 시간 t가 변하더라도 상태확률이 변하지 않는 확률과정

마르코브 성질

확률과정을 통해 알고 싶은 것 --> 과거부터 현재까지 어떤 과정을 거쳤을 때, 다음 단계에서 확률변수가 가지는 특정 값이 될 확률 (=> 조건부 확률)

조건부 확률이 가장 단순한 경우

  • P(Xk+1Xk,Xk1,..,X0)P(X_{k+1}|X_k,X_{k-1}, .., X_0) = P(Xk+1)P(X_{k+1})
    과거와 완전히 독립적인 경우
    --> 시간의 흐름과 관계가 없으므로 분석할 필요가 없음

조건부 확률이 두번째로 단순한 경우

  • P(Xk+1Xk,Xk1,..,X0)P(X_{k+1}|X_k,X_{k-1}, .., X_0) = P(Xk+1Xk)P(X_{k+1}|X_k)
    • XkX_k: 현재
    • Xk1,..,X0X_{k-1}, .., X_0: 과거
  • 현재만이 미래를 결정하는 지표
  • 조건부 확률이 과거와 상관없이 현재로 미래 결정
    --> 복잡한 확률과정 모델 중 가장 단순한 형태

정리

  • 미래는 현재로부터 정해지며, 과거는 영향을 주지 못한다 --> Markov Process

이산시간 마르코브 체인(Discrete-Time Markov Chain; DTMC)

  • 정의: 마르코브 성질을 만족하는 확률 과정
    • chain: 상태공간에 속해 있는 어떤 값들이 셀 수 있는 값일 경우
    • Markov Chain: 확률변수가 셀 수 있는 값 중에 하나를 선택


  • 상태전이확률: i상태에서 다음상태 j가 될 확률 기술
    • 단계별 정의 가능: 첫번째 단계의 i상태가 두번째 단계의 j가 될 확률은 단계별로 다를 수 있음 (일반적인 이산시간 마르코브 체인)

Time-homogeneous DTMC

  • 확률이 시간에 독립적

4-2. 마르코브 프로세스 예시

  • Markov Chain: 확률변수가 셀 수 있는 값들 중에 하나를 선택하는 경우

마르코브 체인 예시 1


  • 마르코브 체인 정의

    • time space: 쥐가 한번 움직일 때 그것을 하나의 단계로 가정 --> 그 단계들의 모음
  • 확률변수 정의

    • XnX_n: n번째 단계에서 쥐의 방 번호
    • X0=1X_0=1
  • Sample path(episode) 예시

  • 마르코브체인 증명

    • 전이확률 정의 가능 시 --> 마르코브체인이라고 할 수 있음

    • 3번방, 9번방은 종료지점으로 다른 방으로 갈 확률이 0임
  • Markov Process: 과거 이력과 상관없이 Markov Property를 따르는 확률과정

마르코브 체인 예시 2(재고 관리)

  • 상황

  • 발주 규칙

  • 가정
    • 주차별 수요에 대한 확률 분포 (수요발생확률을 관리자가 미리 알고 있음)
      • 금요일 발주 시 주말 중 도착 (월요일 판매)
      • 영업일: 월~금(토일 휴무)

    • 물건 품절 시
      • 온라인 쇼핑 예시: 일단 주문만 접수
      • 본 예시: 물건이 없으면 주문 접수 X

문제 정의

  • XnX_n을 n번째 주 금요일 밤 재고 수준이라고 할 때, {Xn:n0X_n:n\geq0}은 마르코브 체인인가?

풀이 과정

마르코브 체인 예시 3

문제 정의

응용

임의 확률과정을 마르코브 체인으로 변환 시 문제점

벽돌깨기 게임

4-3. 마르코브 보상 프로세스

도입

  • 예시: 마르코브 체인에 따라 확률적으로 움직이는 학생 (아래 상태전이 diagram 참조)

    • 다음에 무엇을 할 것인지 결정
      • 과거에 어떤 것을 했는지 상관 X
      • 현재 행동이 다음 행동을 결정 --> 내가 현재 무엇을 했는지가 중요함
    • 상태전이확률로 표시

Markov Reward Process

  • 보상 개념 도입
    • 특정 상태에 제공하는 인센티브
    • 어떤 점수가 특정 상태에 있을 때 리워드 제공

  • 구성요소

에피소드(Episode)

  • 정의: 특정 상태로부터 시작하여 종료 상태까지 (상태,보상) sequence

  • 에피소드별 보상이 다름

GtG_t (Return)

  • t번째 시각 이후의 (감가율이 반영된) 누적 보상
  • 에피소드에서 방문했던 상태별로 얻은 보상의 합

예시

  • SNS reward = -1임

  • 어떤 상태가 더 좋고 나쁜지 평가할 수 있는 지표가 필요
  • 어느 상태에서 시작해야 종료 상태까지 갈 때 보상이 최대가 될 것일까?

가치함수(value function) v(s)v(s)

  • 특정 상태에서의 리턴의 기댓값
  • 상태 s로 부터 시작하는 프로세스로부터 기대할 수 있는 누적보상의 평균
  • 프로세스가 진행됨에 있어, 상태s가 보상측면에서 얼마나 좋은 상태인지 평가하기 위한 지표

가치함수 계산

  • 재귀식을 활용

  • 풀이 예시

정리

마르코브 프로세스

마르코브 보상 프로세스

profile
Data Scientist, Data Analyst

0개의 댓글