[RL] Chapter 2: 마르코프 결정 과정 (MDP)

밑바닥부터 시작하는 딥러닝4를 읽고 정리한 내용입니다✏️.

Chapter 2. 마르코프 결정 과정 (MDP)

밴디트 문제에서는 Agent가 어떤 행동을 취하든 다음에 도전할 문제의 설정은 변하지 않는다.

하지만 현실의 문제들은 다 이와 같지는 않는다.

바둑에서는 에이전트가 어떤 수를 두면 바둑판 위의 돌 배치가 달라진다. 이처럼 에이전트의 행동에 따라 상황이 시시각각 변한다.
그러니 에이전트는 상황이 변하는 것을 고려하여 최선의 수를 두어야 한다.

MDP (Markov Decision Process)

Decision Process : Agent가 Env와 상호작용을 하면서 행동을 결정하는 과정.

위와 같은 Grid World에서는 로봇이 Agent이고 주변이 환경(environment)이다. 에이전트의 행동에 따라 에이전트가 처하는 상황을 상태(State)라고 한다.

• Agent의 목표 : 미래에 얻을 수 있는 보상의 총합 극대화

MDP에서는 Agent와 env사이에 상호작용이 이루어진다. 이때 에이전트가 행동을 취함으로써 State가 변한다. 그에 따라 얻을 수 있는 보상도 달라진다.

2.1 MDP 표현

MDP를 표현하기 위해서 세 요소가 필요하다.

• 상태 전이 (State transition) : 상태는 어떻게 전이되는가?
• 보상 (Reward) : 보상은 어떻게 주어지는가?
• 정책 (Policy) : 에이전트는 행동을 어떻게 결정하는가?

상태 전이(State transition)

상태 전이는 두가지로 나눌 수 있다.

• Determinisitc : 왼쪽 그림과 같이 에이전트가 ‘반드시’ 왼쪽으로 이동
  • \(s'\)은 현재 상태 \(s\)와 행동 \(a\)에 의해 ‘단 하나로’ 결정된다.
  • 함수로는 \(s' = f(s,a)\) 로 표현하고 상태 전이 함수(State transition function)라고 한다.
• Stochastic : 오른쪽 그림과 같이 에이전트가 ‘확률적’으로 이동
  • 현재 상태 \(s\)에서 행동 \(a\)를 했을 때 \(s'\)으로 전이될 확률
  • \(p(s'∣s,a)\)로 표현하고, 상태 전이 확률(State transition probability)라고 한다.

\(p(s'∣s,a)\)가 다음 상태 \(s'\)을 결정하는 데는 ‘현재’ 상태 \(s\)와 행동 \(a\)만을 고려한다.

• 마르코프 성질(Markov property) : 과거의 정보에 상관없이 현재의 정보만 고려한다.
• MDP는 마르코프 성질을 만족한다고 가정하고 상태 전이를 모델링한다.
  • 마르코프 성질을 도입하는 가장 큰 이유 : 문제를 더 쉽게 풀기 위함
  • 과거의 모든 상태와 행동까지 고려하면 조합이 기하급수적으로 많아짐

보상 (Reward)

에이전트가 상태 \(s\)에서 행동 \(a\)를 수행하여 다음 상태 \(s'\)이 되었을 때 얻는 보상을 \(r(s,a,s')\)이라는 함수로 정의하고 보상 함수(Reward function)라고 한다.

정책 (Policy)

정책(Policy) : 에이전트가 행동을 결정하는 방식

• 에이전트는 ‘현재 상태’만으로 행동을 결정할 수 있다. 환경의 상태 전이가 마르코프 성질을 따름

2.2 MDP 문제

MDP의 목표 : 최적 정책(Optimal policy) 즉, 수익이 최대가 되는 정책을 찾는 것이다.

MDP문제는 일회성 과제와 지속적 과제로 나뉜다.

• 일회성 과제(episodic task) : ‘끝’이 있는 문제
  • 예를 들어 바둑, 바둑은 결국 승리/패배/무승부중 하나로 귀결된다.
  • 시작부터 끝까지의 일련의 시도를 에피소드(Episode)라고 한다.
• 지속적 과제(Continuous task) : ‘끝’이 없는 문제
  • 예를 들어 재고 관리, 판매량과 재고량을 보고 최적의 구매량을 결정해야 한다.

수익(Return)

에이전트의 목표 : 수익을 극대화하는 것이다. 수익(\(G_t\)) : 에이전트가 얻는 보상의 합이고 아래와 같이 정의한다.

\(γ\) : 할인율(discount rate)

discount rate를 도입하는 주된 이유는 지속적 과제에서 수익이 무한대가 되지 않도록 방지하기 위함이다.
할인율이 없다면, 즉 r=1 이라면 지속적 과제에서 수익이 무한대까지 늘어난다.

상태 가치 함수(State-value function)

수익을 극대화 하는 것이 에이전트의 목표이다. 하지만 에이전트와 환경이 ‘확률적’으로 동작할 수도 있다. 이러한 확률적 동작에 대응하기 위해서는 기댓값, 즉 ‘수익의 기댓값’을 지표로 삼아야 한다.

상태 \(S_t\) 가 \(s\) 이고 시간 \(t\) 는 임의의 값, 에이전트의 정책은 $π$일때 에이전트가 얻을 수 있는 기대 수익

이처럼 수익의 기댓값을 \(v_π(s)\)로 표기하면 이거를 상태 가치 함수 (State-Value function)이라고 한다.

최적 정책(Optimal policy)

강화 학습의 목표 : 최적 정책을 찾는 것

Q. 최적 정책이란 무엇이고, ‘최적’ 을 어떻게 표현할 수 있을까?

위 그림과 같이 모든 상태에서 \(v_{π'}(s)\) ≥ \(v_π(s)\) 가 성립하면, \(π'\)가 \(π\)보다 나은 정책이다.

이처럼 두 정책의 우열을 가리려면 하나의 정책이 다른 정책보다 ‘모든 상태’에서 더 좋거나 최소한 똑같아야 한다.

최적 정책을 \(π_*\)로 표현한다면 정책 \(π_*\)는 다른 정책과 비교하여 모든 상태에서 상태 가치 함수 \(v_{π_*}(s)\)의 값이 더 큰 정책이다.

• MDP에서는 최적 정책이 적어도 하나는 존재한다.
• 최적 정채의 상태 가치 함수를 최적 상태 가치 함수(optimal state-value function)이라고 한다.

2.3 정리

MDP는 에이전트와 환경의 상호작용을 수식으로 표현한 것이다.

환경에는 상태 전이 확률(또는 상태 전이 함수)과 보상 함수가 있고, 에이전트에는 정책이 있다.

환경과 에이전트가 영향을 주고 받는다.

이러한 틀 안에서 최적 정책을 찾는 것이 MDP의 목표이다.

• 최적 정책 : 모든 상태에서 다른 어떤 정책보다 상태 가치 함수의 값이 더 크거나 같은 정책
• MDP에서 최적 정책은 적어도 하나 존재한다. (증명 가능)

맨 위로 이동하기

RL 카테고리 내 다른 글 보러가기