Zzong's Notes

Markov Decision Process

3 min read

Markov Decision Process

MDP 는 sequential decision-making 문제를 풀기위한 모델을 설정할 때 사용할 수 있는 프레임워크를 의미한다.

A.1) MDP 구성 요소

MDP 는 Markov Reward Process 와 다르게 Action 이 추가된 구성을 가진다.

image-20201021193635194

  • States : (states 는 다양한 형태로 존재할 수 있음)
  • Action:
  • Reward :

MDP 의 time 는 굳이 시간에 대한 개념이 아니라 stages 로 생각하면 좋다.

A.2) Markov Property

Markov property: MDP 의 와 는 무조건 와 에 의해서만 영향을 받음

B) Dynamics of the MDP

time step 에서 를 통해 에서 으로 옮겨서 를 받을 확률

  • 는 definition 이라는 뜻

가능한 모든 dynamics 를 더하면 1 이 된다.

C) State-transition Probabilities

상태 전이 확률은 다음과 같이 계산된다.

  • dynamics of the MDP() 의 three-arguments 버전
  • 에서 받을 수 있는 reward 에 대한 확률을 다 합친 것임

Expected rewards

에서 를 수행했을 때, 받을 수 있는 reward 의 기댓값 (expectation)

  • 에서 를 수행하여 로 이동했을 때, 받을 수 있는 reward 의 기댓값

는 다음과 같음

D) MDP in Recommendation Scenario

  • States: time step 에 존재하는 interaction history 의 representation
  • actions: 추천 가능한 후보 아이템들의 전체 집합
  • Transition probability: agent 가 사용자 feedback 을 받고 state 에서 으로 넘어갈 확률
  • Reward Function : user’s feedback
  • : Discount Factor

E) Related

F) References

링크된 언급

10
bootstrapping

... 한다. 다만, 이렇게 수행하는 방식은 states 가 너무 많은 경우 실행이 불가능하다. 많은 Reinforcement Learning 방법은 DP 에서 요구되는 완전하고 정확한 환경 모델 (MDP) 없이도 bootstrapping 을 수행한다. D) Related bagging

DP (Reinforcement Learning)

DP DP 방식은 MDP 에 대한 optimal solution 을 제공하는 방법이다. 일반적으로 MDP 와 같은 환경에 대한 완벽한 모델이 주어졌을 때 사용하는 알고리즘의 총칭을 의미한다. DP 방식이 optimal...

DRN - A Deep Reinforcement Learning Framework for News Recommendation

.... B) Introduction 논문에서 제안한 DQN 방식과 기존 강화학습을 이용한 방식의 차이점이 있다. MAB 기반 방식은 미래 보상에 대해서 명시적으로 모델링을 수행하지 않는다. 그리고 MDP 기반 방식은 state 표현을 위해 discrete 한 유저 로그를 사용하므로 대용량 시스템에 대하여 확장성이 부족하다. 각 유저의 활동성 점수를 유지하기 위해서, 제안한 방식은 user re...

dynamics

Dynamics MDP 에서 정의하는 dynamics 는 다음과 같다. “t timestamp 에서 action a 를 통해 state s 에서 state s& 039; 으로 옮겨서 reward r 을 받을 확률” ...

Markov Chain

...이 확률을 나타낸 확률적 모델 (stochastic model) 이다. Markov Chain 은 transition Matrix 을 이용해 표현된다. Markov chain 을 이해하는 것이 MDP 의 근간을 이해하는 것이다. 2. States 에 따른 분류 2.1. Communicate state i 에서 j 로 도달할 수 있다면, reachable 하다고 표현한다. 만약, j 에서 i...

Monte Carlo Method(RL)

...법은 경험 (experience) 이 필요하다. 경험이란 환경과의 상호 작용을 통해 얻어지는 일련의 states, actions 그리고 rewards 의 sample 을 의미한다. MC 방식은 MDP 를 알 수 없는 상황에서 value function 을 추정한다는 관점에서 model free prediction 방식으로 불린다. B) Monte Carlo Prediction 우선 몬테 카...

partially observable Markov decision process

Partially Observable Markov Decision Process POMDP 는 tuple \langle S, A, O, P, R, Z, \gamma\rangle 에 의해 표현될 수 있다. 여기서 O 는 관찰 가능한 것들의 집합이고, Z 는...

policy

...olicy 란 주어진 states 에서 actions 에 대한 확률 분포를 의미하며 \pi 로 표현한다. \pi(a \mid s)=P\left[A {t}=a \mid S {t}=s\right] MDP 에서 RL 의 목표는 expected cumulative reward(expected return) 값을 최대화 하는 policy 를 찾는 것이다. Related References

Reinforcement Learning

...learning 기법 중 하나. B) For RS A Survey on Reinforcement Learning for Recommender Systems C) Related Markov Decision Process, dynamic programming, Monte Carlo Method, temporal difference N step Bootstrapping Policy Gradien...

state-value function

...state value function v {\pi}(s) 이라 부른다. 이는 state s 에서 시작할 때 얻을 수 있는 expected discounted return 값을 의미한다. 그리고 MDP 에서 이 함수는 policy 를 위해 정의된 것이다. policy 에 의해 전이 확률 행렬이 결정되는 것을 고려해볼 때, policy 를 변경한다는 것은 결국 다른 state value fun...