MDP and Planning

머신러닝에서 주로 세가지로 나눠서 얘기를 한다. 지도 학습, 비지도 학습, 강화 학습.

강화 학습은 그중에서도 순차적 의사결정이라는 특수한 문제를 담당해서 해결하는 프레임워크이다.

우리 삶은 연속적인 결정의 연속이다

예를 들어 아침에 일어나서 무엇을 먹을지, 옷을 뭘 입을지, 지하철을 탈지 버스를 탈지 등 하루 종일 '결정'을 계속 내리고,

이 모든 결정이 하나로 연결돼서 결과를 만든다.

우리는 시행착오(trial-and-error)로 배운다

아기가 기어 다니는 걸 배울 때 생각하면, 처음에는 넘어지고, 엎어지고, 좌절하지만 계속 시도하면서 조금씩 나아짐.

→ 즉, 좋은 결정을 만드는 ‘순서’를 연습과 실패를 통해 배운다는 것.

 

강화 학습이 사람 혹은 동물이 시행착오를 통해서 자연스럽게 문제를 해결해 나가는 방법을 학습하는 것을

수학적으로 Formulation한 형태라고 볼 수 있음.

Agent (행동하는 주체): 예를 들어 아기, 로봇, AI

World (환경): 세상, 혹은 Agent가 행동하는 대상

이 둘 사이에 '순환'이 있다.

Agent가 World에 행동(Action)을 취함

예를 들어, 아기가 기어가서 장난감을 잡으려고 한다.

World는 관찰/보상(Observation/Reward)을 준다.

 

보상을 보면서 매 관측에 맞는 행동을 해나가는 것이다.

행동 하는 것의 목표는 결국 이러한 일련의 행동들을 통해서 계속해서 보상을 받아 나갈 텐데,

이런 미래에 기대되는 보상의 합을 최대화하는 행동들을 고르는 것이 우리의 목표가 된다.

 

순차적 의사결정 문제의 재밌는 점은 우리가 당장 행동을 해서 보상을 받는 것과 일련의 행동들을 해서 나중에 큰 보상을 받는 것,

이렇게 2가지 중에서 더 좋은 것을 골라 낼 수 있는 능력이 있어야 된다는 것이다.

이렇게 계속 행동과 결과가 반복되면서 학습이 일어난다.

 

Markov Decision Processes (MDP)

1. Process

시간에 따라 바뀌는 시스템을 다룬다는 것. Continous한 시간이 아니라 Time Step별로 행동을 하는 상황을 가정함.

Discrete time (이산 시간): 시간을 1초, 2초, 3초처럼 끊어서 생각함

아기가 1초마다 한 번씩 움직인다고 생각하면 각각의 시간 단계에서 어떤 일이 일어나는지를 추적하는 방식.

 

2. Markov

의사 결정을 내리기 위해 필요한 모든 정보를 관측할 수 있다

즉, 현재 상황을 전부 관측할 수 있기 때문에 과거 기록은 필요 없다.

아기가 지금 "기어가고 있다"라는 상태만 보면, 다음 행동(손을 뻗는다, 무릎을 굽힌다 등)을 결정할 수 있음.

굳이 "1분 전엔 어떻게 했는지" 몰라도 괜찮다. 이것이 Markov 성질임

 

3. Decision

매 Time Step마다 우리가 행동을 선택(결정)해야 한다.

그 목적은 보상(reward)을 최대화하거나, 비용(cost)을 최소화하는 것!

아기가 “왼쪽으로 가면 장난감을 빨리 잡을 수 있다”는 걸 알면 그런 결정을 반복해서 더 많은 보상을 얻을 것.

상태, 행동, 보상, 시간 개념까지 포함하여 수학적으로 정확하게 모델링 한 것이 MDP 이다.

Markov Processes 구조

- 점진적으로 모델이 확장되는 순서에 따라서 설명하겠다.

 

Markov Processes = (S, P)

- S (State): 가능한 모든 상태들

예: 아기의 위치, 자세, 눈앞에 있는 장난감 등

- P (Transition Probability): 상태가 어떻게 바뀌는지에 대한 확률

예: 아기가 앞으로 한 번 움직이면 ‘장난감 근처에 도달할 확률이 0.8’

 

Markov Reward Processes = (S, P, R, γ)

- R (Reward): 상태에서 받는 보상

예: 장난감을 잡으면 +10점, 그냥 바닥에 있으면 0점

- γ (Gamma): 미래 보상의 중요도를 조절

→ 0에 가까우면 지금 보상만 중요한 반면, 1에 가까우면 미래까지 고려함

 

Markov Decision Processes = (S, A, P, R, γ)

- A (Action): 우리가 선택할 수 있는 행동들

예: 앞으로 기기, 오른쪽으로 돌기, 손 뻗기 등

 

Markov Reward Processes에서 Discount Factor 가 나오는데,

MDP에서 보상을 어떻게 평가하는지, 이전까지는 행동을 선택해서 좋은 보상을 얻자 는 개념적인 설명

그렇다면 이젠 좋음이란 도대체 수학적으로 어떤 기준이냐?를 정확하게 정의하는 단계

 

Return & Value Function

Horizon 𝐻

에이전트가 활동하는 시간의 길이

예: 아기가 기어가서 장난감을 잡기까지 5초가 걸린다면 → 그 에피소드의 Horizon은 5

유한한 경우(finite): 예: 10초 후 끝

무한한 경우(infinite): 계속 반복되는 게임이나 환경

 

Return 𝐺𝑡

시간 𝑡부터 Horizon까지 받은 보상의 총합

그런데 단순히 더하는 게 아니라, 미래 보상일수록 덜 중요하게 생각한다.

→ 이걸 "할인(discount)"한다고 함.

 

𝛾는 Discount Factor (할인율)

지금 사탕 받는 건 1.0점

내일 사탕 받는 건 0.9점처럼 미래는 조금 덜 좋게 봄.

당장의 보상이 사실 젤 중요한 거니까.

 

State Value Function 𝑉(𝑠)

어떤 상태 𝑠에서 시작했을 때 기대되는 전체 보상

지금 이 상태에 있으면 앞으로 받을 보상 총합이 몇 점일까? -> 높으면 좋은 state 이다.

Discount Factor

왜 할인율이 필요할까?

 

수학적으로 무한대로 누적되는 보상을 막기 위해서임.

(무한히 계속 보상을 더하면 값이 무한대가 될 수도 있어서)

 

현실적으로도 사람들은 미래 보상을 덜 중요하게 여김

당장 받는 돈이 더 좋고 나중에 받을 돈은 불확실하니까 덜 좋게 생각함.

 

γ의 의미

𝛾 = 0 지금 보상만 중요

당장 한 번 이기고 말겠다는 전략

𝛾 = 1 미래 보상도 똑같이 중요

장기적으로 최고의 전략을 원함

 

그래서 즉시 보상과 장기 보상 사이의 균형을 조절하기 위해 Discount factor가 필요하다.

 

MRP (Markov Reward Process) 상황에서 벨만 방정식(Bellman Equation)을 이용해 상태의 가치를 계산하는 방법

"지금 점수 + 미래 기대 점수"가 바로 현재 상태의 가치

이걸 Bellman Equation 이라고 부른다.

Matrix Form of Bellman Equation for MRP

앞의 수식을 행렬로 바꾼 것이다.

 

앞의 수식을 다시 정리해서 계산 가능한 형태로 만든 것.

즉, 수학적으로 직접 V를 계산하려면 이 역행렬을 구하면 된다.

 

이렇게 풀면 너무 오래 걸리기 때문에 Iterative Algorithm이 등장함.

MRP에서는 보상의 개념이 있었지만, MDP에서는 행동이라든가 하는 개념은 따로 없다.

중간 값인 Value Function을 통해서 구해낸다는 점에서 이 알고리즘을 Dynamic Programming 이라고 부르는 부분이 있음.

 

여기서 추가된 것은 행동의 집합이 정의가 되었다. 

행동하는 것에 따라서 상태가 어떻게 바뀔지가 바뀌어 나가게 된다.

 

보상함수 역시 이 행동에 기반해서 정의가 된다.

그래서 또 Markov 성질 역시 여기서도 비슷하게 기존에 independent 하다 하지만, 이 직전 Step의 State-action이 주어지면 바뀌게 된다.

기존에 History에서도 기존에 reward-state-action 이것들이 다 들어가야 되지만 이것이 independent 하다. 이런 Markov 성질이 들어가게 된다.

Policy는 “각 상태(State)에서 어떤 행동(Action)을 할지”를 정하는 규칙

예를 들어 로봇이 미로에 있다면,

State: “벽 앞에 있음”

Policy: “오른쪽으로 돈다”

이런 매핑이 바로 Policy 이다.

 

여기서 Policy를 Stationary하게 정상적으로 잡는다.

 

정책의 종류

Deterministic Policy (결정적 정책)

상태가 주어지면 행동이 딱 하나로 정해짐.

예: “배고픈 상태 → 밥 먹기”, “졸린 상태 → 잠자기”

MDP 할때는 Deterministic Policy만으로도 많은 것을 설명할 수 있음.

 

Stochastic Policy (확률적 정책)

상태가 주어져도 여러 행동 중 확률적으로 고름.

예: “신호등 앞(상태)”에서 70% 확률로 “왼쪽으로 가기”, 30% 확률로 “직진하기”

Stochastic Policy는 탐험(Exploration)이 필요한 상황에서 자주 쓰인다.

 

MDP와 Policy가 합쳐지면 다시 MRP로 단순화된다

MDP + Policy = MRP

MDP는 상태, 행동, 보상, 전이확률이 있는 복잡한 구조입니다.

하지만 정책 π(a|s)가 주어지면 “상태에서 어떤 행동을 할지”가 확률적으로 정해집니다.

따라서 행동(Action)을 고려할 필요가 없어지고, 다시 “상태와 보상만 있는 MRP” 형태로 단순화됩니다.

앞으로는 “주어진 정책 π의 가치(Value)를 어떻게 평가할까?”라는 문제를 MRP 도구(벨만 방정식, 반복 알고리즘)로 풀 수 있음.

 

정책 π가 주어지면 MDP는 MRP가 된다

따라서 MRP에서 썼던 iterative value computation 방법을 그대로 쓸 수 있음.

현재 상태에서 정책에 따라 행동을 골라 보상과 미래 기대 보상을 더하는 식

이 과정을 반복하면 정책 π가 주어졌을 때 상태 가치 함수 V^π(s)를 구할 수 있다.

 

그래서 이렇게 하면 정책이 주어졌을 때 이것에 대한 상태의 가치를 알 수 있다. 그러면 그 정책이 불러올 수 있는 기대 보상의 합을 계산할 수 있다.

기대 보상의 합을 통해서 정책의 가치를 평가하고, 정책들을 비교하고 더 좋은 정책을 골라낼 수 있다는 얘기가 된다.

4×4 격자판 (16칸)

왼쪽 위(1)와 오른쪽 아래(16)는 터미널 상태 (게임 종료).

나머지 14칸이 non-terminal states.

 

상태와 행동

상태 S = {1, 2, …, 14}

행동 A = {위, 아래, 오른쪽, 왼쪽}

 

규칙

보상 R(s,a) = -1 (한 번 움직일 때마다 -1점)

즉, 목표는 최대한 빨리 터미널에 도착하는 것.

전이는 결정적(deterministic).

ex) 상태 5에서 오른쪽 가기 → 항상 6으로 간다.

경계에 부딪히면 그대로 제자리에 머문다.

 

Policy π₀: 네 방향을 똑같은 확률(25%)로 무작위 선택하는 랜덤 정책.

Gridworld 예제는 실제로 수치로 어떻게 가치가 업데이트되는지 보여준다.

Value Function이 더 높은 곳으로 가는 것이 좋은 정책이 된다.

정책들 사이의 우열을 정의한다.

정책 π가 π′보다 좋다(π ≥ π′)고 말하려면, 모든 상태에서 가치가 더 크거나 같아야 한다.

어떤 MDP든 항상 최적 정책 π*이 존재한다.

즉, 모든 정책 중에서 가장 좋은 정책이 있고, 그 정책은 모든 상태에서 가장 높은 가치를 달성한다.

 

로봇이 미로에서 탈출하는 문제

정책A: 무작위로 움직임 -> 평균 20턴 후 탈출

정책B: 올느쪽으로 가다가 막히면 아래로 _> 평균 10턴 후 탈출

이때 정책 B가 정책 A보다 더 좋은 정책(가치가 높음)

결국 최적 정책은 평균 탈출 시간이 가장 짧은 규칙이 될 것이다.

우리는 이제 최적 정책은 존재한다는 걸 알았다.

특히 무한 시계열(infinite horizon) MDP에서는, 최적 정책이 결정적(deterministic)이고 고정(stationary)되어 있음을 보장한다.

결정적: 주어진 상태에서 항상 같은 행동을 선택한다.

고정: 시간이 흘러도 바뀌지 않고, 오직 현재 상태에만 의존한다.

그런데 가능한 정책의 수는 매우 많다.

정책의 수 = |A|^|S|

상태가 100개, 행동이 4개라면 4^100개의 정책이 가능 → 어마어마하게 크다.

따라서 단순히 모든 정책을 다 탐색하는 것은 불가능하다.

더 효율적인 정책 탐색 알고리즘이 필요하다.

 

최적 정책을 찾는 방법인 Policy Iteration에 대해서 배우자.

 

Policy Evaluation (정책 평가)

현재 정책 π_i에 대해, 모든 상태의 가치 V^π_i(s)를 계산.

 

Policy Improvement (정책 개선)

방금 계산한 가치 함수 V^π_i(s)를 바탕으로, 더 나은 행동을 고르는 새로운 정책 π_{i+1}을 만든다.

이 과정을 정책이 더 이상 바뀌지 않을 때까지 반복하면, 최적 정책 π*에 도달한다.