Markov Decision Process

Model: Mathematical models of dynamics and reward Policy: Function mapping agent’s states to actions Value function: future rewards from being in a state and/or action following a particular policy

Markov Processes §

graph LR
    World -->|State| Agent
    World -->|Reward| Agent
    Agent -->|Action| World

Markov Property §

State $s_t$ is Markov if and only if:

$p(s_{t+1}|s_t,a_t)=p(s_{t+1}|h_t,a_t)$ $t$ is timestep $a_t$ is action $h_t$ is history recall, sequence of all previous action and rewards and states those we have seen up until current time point

อธิบาย Markov Property บอกเราว่า future state จะขึ้นอยู่กับ current state เท่านั้น และจะไม่ขึ้นกับ sequence of states/events ก่อนหน้า current state

เหมือนกับบอกว่า Process นี้ memoryless, states หรือ actions ก่อนหน้า current state จะไม่ส้งผลต่อ future state

Markov Process / Markov Chain §

Markov Process is stochastic process that satisfy Markov property $\to$ Random process where the future state depends only on the current state and not on the sequence of events that led to the current state

Markov Chain is Markov process that is discrete in time

---

Definition

• $S$ is a (finite) set of stats ($s\in S$)
• Transition/Dynamic model $P=p(s_{t+1}=s^{{}^{\prime }}|s_t=s)$

---

มีเซ็ทของ states + มี dynamic model ที่ระบุ probability ที่จะไปที่ state ต่อไปเมื่อให้ค่าของ state ปัจจุบัน + ที Markov property = Markov Process

NOTE: no reward and action related at the moment

Notation

การที่เราเขียน $p(a|b)$ มันคือ บอกว่า ถ้าเราให้ค่า b ไปจะมีโอกาส $P=p(a|b)$ ที่จะได้ a หรือถ้าเป็น $p(s_{t+1}=s^{{}^{\prime }}|s_t=s)$ คือ ถ้าเรามี state $s_t$ จะมีโอกาส $P=p(s_{t+1}=s^{{}^{\prime }}|s_t=s)$ ที่จะไป state $s_{t+1}$

Example and Transition Matrix §

สมมติเรามีโมเดลอากาศที่มีสอง state ฝนตก หรือ แดดออก Markov Chain จะ model สภาพอากาศเป็น random process แบบนี้

• ถ้า แดดออก วันนี้ พรุ่งนี้มีโอกาส 70% แดดออก 30% ฝนตก
• ถ้า ฝนตก วันนี้ พรุ่งนี้มีโอกาส 40% แดดออก 60% ฝนตก

เราสามารถเขียน transition matrix ได้แบบนี้

$$P=\left(\begin{array}{cc}0.7& 0.3\\ 0.4& 0.6\end{array}\right)$$

Markov Reward Processes (MRPs) §

Markov Reward Process is a Markov Chain + rewards

---

Definition

• $S$ is a (finite) set of stats ($s\in S$)
• Transition/Dynamic model $P=p(s_{t+1}=s^{{}^{\prime }}|s_t=s)$
• $R$ is a reward function $R(S_t=s)=Expected(r_t|s_t=s)$ (Expected reward you get from being in the state)
• Discount factor $\gamma \in [0,1]$ (immediate reward | future reward)

---

NOTE: no action related at the moment

Expected Return §

เป้าหมายของ MRP คือการคำนวณ expected return ของ state $s$ โดยสมการ

$V(s)=E[{\sum }_{t=0}^{\infty }{\gamma }^{t}R(s_t)\mid s_0=s]$

แต่จะเห็นว่ามันดูยุ่งยากเพราะฉะนั้นเราจะมาใช้อีกวิธีในการคำนวณ expected return ด้วยการ บวกค่าระหว่าง immediate reward + discounted future reward

Bellman Equation for MRP §

เราสามารถคำนวณ expected return แบบ recursively ได้ด้วย Bellman Equation

$V(s)=R(s)+\gamma \sum _{s^{\prime }}P(s^{\prime }|s)V(s^{\prime })$

• $R(s)$ is the immediate reward obtained from state $s$,
• $\gamma$ is the discount factor,
• $P(s^{\prime }\mid s)$ is the probability of transitioning from state $s$ to state $s^{\prime }$,
• $V(s^{\prime })$ is the value function of the next state $s^{\prime }$.

Markov Decision Processes (MDPs) §

Markov Decision Process is Markov Reward Process + actions

---

Definition

• $S$ is a (finite) set of stats ($s\in S$)
• $A$ is a (finite) set of actions $a\in A$
• Transition/Dynamic model for each action, $P=p(s_{t+1}=s^{{}^{\prime }}|s_t=s,a_t=a)$
• $R$ is a reward function $R(S_t=s)=Expected(r_t|s_t=s)$ (Expected reward you get from being in the state)
• Discount factor $\gamma \in [0,1]$ (immediate reward | future reward)

MDP is a tuple: $(S,A,P,R,\gamma )$

---

MDP Policy §

Policy จะบอกเราว่าต้องทำ action อะไรในแต่ละ state --- Specify what action to take in each state

• Can be deterministic (ที่ state ไหนจะใช้ action ไหน) or stochastic (action จะถูกเลือกแบบสุ่ม (มี probability))

สามารถเขียนได้โดย $\pi (a|s)=P(a_t=a|s_t=s)$

เราสามารถมองได้ว่า

MDP + $\pi (a|s)$ = Markov Reward Process (ถ้าเรา fixed policy)

MDP Policy Evaluation §

$V_k^{\pi }(s)=R(s,\pi (s))+\gamma \sum _{s^{\prime }\in S}p(s^{\prime }|s,\pi (s))V_{k-1}^{\pi }(s^{\prime })$