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

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 })$

เราต้องการคำนวณ ค่า value ของแต่ละ state ภายใต้ policy ที่กำหนดไว้ $\pi$ ซึ่งก็คือการคำนวณว่า ถ้าเราเริ่มจาก state $s$ และทำตาม policy $\pi$ เราจะได้ expected return เท่าไหร่

ในกรณีนี้เราใช้การคำนวณแบบ iterative (เชิงซ้ำ) โดยเริ่มจากค่าเริ่มต้นของ value function และทำการอัปเดตซ้ำไปเรื่อย ๆ ตามสูตร

โดยที่:

• $V_k^{\pi }(s)$ คือ ค่าของ state $s$ ในรอบที่ $k$ ภายใต้ policy $\pi$

• $R(s,\pi (s))$ คือ ค่าผลตอบแทนทันที (immediate reward) ที่ได้จากการทำ action ตาม policy ที่ state $s$

• $p(s^{\prime }\mid s,\pi (s))$ คือ ความน่าจะเป็น ที่จะย้ายไปยัง state $s^{\prime }$ หลังจากทำ action ตาม policy ที่ state $s$

• $\gamma$ คือ discount factor ที่ใช้ลดค่าผลตอบแทนในอนาคต (เช่น $\gamma =0.9$ หมายถึงให้ความสำคัญกับอนาคต 90%)

---

กระบวนการประเมิน Policy

1. กำหนดค่าเริ่มต้นของ $V_0(s)$ สำหรับทุก $s\in S$ (เช่น เริ่มจากศูนย์)
2. ทำการอัปเดตค่า $V_k(s)$ ตามสูตรด้านบน จนกว่าค่าจะ คงที่ หรือ เปลี่ยนแปลงน้อยมาก (convergence)
3. ผลลัพธ์ที่ได้คือ $V^{\pi }(s)$ ซึ่งบอกว่า state $s$ มี expected return เท่าใดเมื่อทำตาม policy $\pi$