一、基礎概念
Markov Decision Process（MDP）是以馬爾科夫過程為基礎，加入決策變數而形成的數學模型。它主要包含以下成分：
狀態（State）：描述系統當前的所有狀態，可能是一維或多維向量。在某一時刻，系統處於某個具體的狀態。
決策（Decision）：指當前狀態下擬採取的行動或策略。決策的選擇受到限制，如有些狀態下只有一個可選擇的決策，有些則有多個不同的決策可供選擇。
獎勵（Reward）：在當前狀態下，由於做出該決策所獲得的收益或者價值。
轉移概率（Transition Probability）：指在某個狀態下，執行某個決策轉移到另一個狀態的概率。在馬爾科夫過程中，當前狀態的下一個狀態僅與當前狀態相關，與之前的狀態和決策無關。
MDP模型可以用以下狀態轉移矩陣表示：
s1 s2 s3 ... sn
a1,s1 -> s'1 p11 p12 p13 ... p1n
a1,s2 -> s'2 p21 p22 p23 ... p2n
a1,s3 -> s'3 p31 p32 p33 ... p3n
... ... ... ... ... ...
a1,sn -> s'n pn1 pn2 pn3 ... pnn
a2,s1 -> s'1 q11 q12 q13 ... q1n
a2,s2 -> s'2 q21 q22 q23 ... q2n
a2,s3 -> s'3 q31 q32 q33 ... q3n
... ... ... ... ... ...
a2,sn -> s'n qn1 qn2 qn3 ... qnn
... ... ... ... ...
am,s1 -> s'1 r11 r12 r13 ... r1n
am,s2 -> s'2 r21 r22 r23 ... r2n
am,s3 -> s'3 r31 r32 r33 ... r3n
... ... ... ... ... ...
am,sn -> s'n rm1 rm2 rm3 ... rmn
其中，$s_i$表示第$i$個狀態，$a_j$表示第$j$個決策，$s’_k$表示第$k$個狀態。$p_{i,k}$表示在狀態$s_i$下，執行決策$a_1$，轉移到狀態$s’_k$的概率；$q_{i,k}$表示在狀態$s_i$下，執行決策$a_2$，轉移到狀態$s’_k$的概率；$r_{i,k}$表示在狀態$s_i$下，執行決策$a_m$，轉移到狀態$s’_k$的概率。
二、價值函數
價值函數是MDP中的一個核心概念，用於評價某個狀態或狀態集合的價值，即在這個狀態或狀態集合下，執行某個策略所能獲得的期望獎勵。
具體來說，對於某個狀態$s$，我們定義它的價值函數為$V(s)$，表示在狀態$s$下，執行我們所選擇的策略能夠獲得的期望獎勵。進一步地，我們可以將所有狀態的價值函數組合成一個向量：
$$
V = [V(s_1), V(s_2), …, V(s_n)]^T
$$
同樣，對於某個狀態$s$和一個決策$a$，我們定義它的價值函數為$Q(s,a)$，表示從狀態$s$開始，採取決策$a$，以後策略的預期收益。進一步地，我們可以將所有狀態和所有決策的價值函數組合成一個$nxm$維的矩陣$Q$：
$$
Q = \begin{bmatrix} Q(s_1,a_1) & Q(s_1,a_2) & … & Q(s_1,a_m) \\ Q(s_2,a_1) & Q(s_2,a_2) & … & Q(s_2,a_m) \\ … & … & … & … \\ Q(s_n,a_1) & Q(s_n,a_2) & … & Q(s_n,a_m) \end{bmatrix}
$$
三、策略（Policy）
策略指從狀態到決策的映射，即在每個狀態下採取哪個決策。如果策略是確定性策略，那麼對於同一個狀態，總是選擇相同的決策；如果是隨機策略，那麼在相同的狀態下，每個決策的選擇是按一定概率分布隨機選擇的。
我們可以使用$\pi(a|s)$表示從狀態$s$開始採取決策$a$的概率。同時，我們也可以使用$\pi$來表示整個MDP中的策略，即$pi = [\pi(a|s_1), \pi(a|s_2), …, \pi(a|s_n)]$，其中$s_1, s_2, …, s_n$是所有可能的狀態。
四、MDP的求解
1. 值迭代
值迭代是解決MDP的最簡單的方法。它的思路很簡單：我們從某個初始狀態開始，按照某個策略，不斷地更新當前狀態的價值函數，直到價值函數不再變化。這時，我們可以得到這個策略的「最優」價值函數。因此，我們可以選擇每個狀態中最具有代表性的決策，組成一個最優策略。該過程中，我們使用式子（1）來更新價值函數：
$$
V(s) = \max_{a_i \in A(s)}\sum_{s’\in S}p(s’ | s, a_i) [ R(s, a_i, s’) + \gamma V(s’) ]
$$
其中，$A(s)$表示在狀態$s$下可選擇的決策的集合，$p(s’|s,a_i)$表示根據$s$和$a_i$轉移到$s’$的概率，$R(s,a_i,s’)$表示在狀態$s$下執行決策$a_i$轉移到狀態$s’$時所獲得的獎勵，$\gamma$表示考慮未來遠期收益的折扣因子。
2. 策略迭代
策略迭代是一種交替進行策略評估和策略改進的演算法。在每輪迭代中，首先通過與當前策略不同的一些策略，計算出它們的價值函數，然後根據新的價值函數來改進策略，最後返回一個新的策略。迭代循環直到策略收斂。在策略評估過程中，有兩種方法用來計算一個策略的價值函數。一種是採用而非確定性策略（stochastic policy），計算價值函數時考慮採用每個決策的概率。另一種是採用確定性策略（deterministic policy）。
下面是策略迭代的代碼示例：
import numpy as np
# 策略評估
def policy_evaluation(transitions, policy, gamma=1.0, theta=0.00001):
num_states = transitions.shape[0]
V = np.zeros(num_states)
while True:
delta = 0
for state in range(num_states):
v = 0
for action, next_states in enumerate(transitions[state]):
for next_state in next_states:
prob, reward = next_state[0], next_state[1]
v += policy[state][action] * prob * (reward + gamma * V[next_state[2]])
delta = max(delta, abs(v - V[state]))
V[state] = v
if delta < theta:
break
return np.array(V)
# 策略改進
def policy_improvement(transitions, policy_eval_fn=policy_evaluation, gamma=1.0):
num_states, num_actions = transitions.shape[0], transitions.shape[1]
policy = np.ones([num_states, num_actions]) / num_actions
while True:
policy_stable = True
value_function = policy_eval_fn(transitions, policy, gamma)
for state in range(num_states):
chosen_action = np.argmax(policy[state])
action_values = np.zeros(num_actions)
for action in range(num_actions):
for next_state in transitions[state][action]:
prob, reward = next_state[0], next_state[1]
action_values[action] += prob * (reward + gamma * value_function[next_state[2]])
best_action = np.argmax(action_values)
if chosen_action != best_action:
policy_stable = False
policy[state] = np.eye(num_actions)[best_action]
if policy_stable:
return policy, value_function
五、總結
本文介紹了MDP的基本概念，包括狀態、決策、獎勵和轉移概率，在此基礎上進一步介紹了價值函數和策略的概念。接著，我們討論了兩種常用的MDP求解方法：值迭代和策略迭代。值迭代通過不斷找到最大價值函數來推導出最優決策。而策略迭代則通過不斷改進策略，來得出最優策略。最後，我們給出了策略評估和策略改進的示例代碼。
原創文章，作者：DZSP，如若轉載，請註明出處：https://www.506064.com/zh-tw/n/150125.html
微信掃一掃 
支付寶掃一掃 