马尔科夫决策过程

马尔科夫过程

马尔科夫性： 系统的下一个状态 St+1 S t + 1 <script type="math/tex" id="MathJax-Element-64">S_{t+1}</script>仅与当前状态有关系，而与如何之前的状态没有关系。也就是说，下一个状态并不取决于之前的状态。（不具备记忆性?）

定义： 一个状态 St S t <script type="math/tex" id="MathJax-Element-65">S_t</script>具备马尔科夫性，当且仅当： P(St+1|St)=P(St+1|St,St−1,⋯,S1) P ( S t + 1 | S t ) = P ( S t + 1 | S t , S t − 1 , ⋯ , S 1 ) <script type="math/tex" id="MathJax-Element-66">P(S_{t+1}|S_t) = P(S_{t+1}|S_t,S_{t-1},\cdots, S_1)</script>
从这个定义中可以得知，之前的状态如何并不会影响下一步的状态。

对于一个马尔科夫状态 s s <script type="math/tex" id="MathJax-Element-67">s</script>和后续状态 s ′ <script type="math/tex" id="MathJax-Element-68">s'</script>，其间的状态转移概率可以定义为：

Pss′=P(St+1=s′|St=s) P s s ′ = P ( S t + 1 = s ′ | S t = s )
<script type="math/tex; mode=display" id="MathJax-Element-69"> P_{ss'} = P(S_{t+1} = s' | S_t = s) </script>

假设一共有 n n <script type="math/tex" id="MathJax-Element-70">n</script>个状态，且都具备马尔科夫性，那么它们之间的转换概率可以使用矩阵表示：

P = | p 11 ⋯ p 1 n ⋮ ⋱ ⋮ p n 1 ⋯ p n n |
<script type="math/tex; mode=display" id="MathJax-Element-71"> P= \begin{vmatrix} p_{11}& \cdots & p_{1n} \\ \vdots & \ddots &\vdots \\ p_{n1}&\cdots& p_{nn} \end{vmatrix} </script>

矩阵行表示当前状态，列表示下一个状态，对应的值为两个状态转移的概率。因此，可以得知每列的和为1。

一个马尔科夫过程是无记忆的随机过程，例如一个随机的状态序列，其中每个状态都具备马尔科夫性。马尔科夫过程（马尔科夫链）可以定义为一个元组（tuple） <S,P> < S , P > <script type="math/tex" id="MathJax-Element-72"></script>,其中 S S <script type="math/tex" id="MathJax-Element-73">S</script>是一个组数目有限的状态， P <script type="math/tex" id="MathJax-Element-74">P</script>是状态转移概率矩阵。
马尔科夫过程
$$

马尔科夫奖励过程

马尔科夫奖励（reward）过程是一个带值得马尔科夫链。通常可以被定义为一个元组 <S,P,R,γ> < S , P , R , γ > <script type="math/tex" id="MathJax-Element-75"></script>,其中 S S <script type="math/tex" id="MathJax-Element-76">S</script>是一个有限的状态集; P <script type="math/tex" id="MathJax-Element-77">P</script>是状态转移概率矩阵; R R <script type="math/tex" id="MathJax-Element-78">R</script>是回报函数， R s = E [ R t + 1 | S t = s ] <script type="math/tex" id="MathJax-Element-79">R_s = E[R_{t+1} | S_t = s]</script>; γ γ <script type="math/tex" id="MathJax-Element-80">\gamma</script>是衰减因子， γ∈[0,1] γ ∈ [ 0 , 1 ] <script type="math/tex" id="MathJax-Element-81"> \gamma \in [0 , 1] </script>。

回报（return）

回报函数 Gt G t <script type="math/tex" id="MathJax-Element-82">G_t</script>是从时间步 t t <script type="math/tex" id="MathJax-Element-83">t</script>之后的总的衰减奖励。

G t = R t + 1 + γ R t + 2 + ⋯ = ∑ k = 0 γ k R t + k + 1
<script type="math/tex; mode=display" id="MathJax-Element-84">G_t = R_{t+1} + \gamma R_{t+2}+\cdots =\sum_{k=0}^{} \gamma^k R_{t+k+1}</script>
衰减因子的值会影响后续状态转移的回报值。 γ γ <script type="math/tex" id="MathJax-Element-85">\gamma</script>小则更注重短期(myopic)回报$$；相应地
，$\gamma$若是较大，则表示更加注重长期（far-sight）回报。
回报

为什么需要衰减因子？
1）避免在马尔科夫回环中产生无限大的值
2）未来并不不确定，因此不需要全部回报
3）符合人类的实践行为—注重眼前效益
…

状态价值函数（value function）

价值函数描绘的是状态的长期价值。一个状态的回报值与其形成的马尔科夫链有关系，不同的链具有不同的回报值。因此，一个马尔科夫随机过程中状态 s s <script type="math/tex" id="MathJax-Element-86">s</script>的状态价值函数可以定义为其回报的期望：

v ( s ) = E [ G t | S t = s ]
<script type="math/tex; mode=display" id="MathJax-Element-87"> v(s) = E[G_t | S_t = s] </script>

状态价值函数

贝尔曼方程

从给出的例子中可以看出，马尔科夫链是可以存在回环的，这就回给求回报时带来一定的困难。尤其当 γ≠0 γ ≠ 0 <script type="math/tex" id="MathJax-Element-88">\gamma \neq 0 </script>时。通过观察所定义的状态价值函数，它可以分解为直接回报和后继状态的衰减值：

v(s)v(s)=E[Gt|St=s]=E[Rt+1+γRt+2+γ2Rt+3+⋯|St=s]=E[Rt+1+γ(Rt+2+γRt+3+⋯)|St=s]=E[Rt+1+γGt+1|St=s]=E[Rt+1+γv(St+1)|St=s]=E[Rt+1+γv(St+1)|St=s]=E[Rt+1|St=s]+γE[v(St+1)|St=s]=Rs+γ∑s′∈SPss′v(s′) v ( s ) = E [ G t | S t = s ] = E [ R t + 1 + γ R t + 2 + γ 2 R t + 3 + ⋯ | S t = s ] = E [ R t + 1 + γ ( R t + 2 + γ R t + 3 + ⋯ ) | S t = s ] = E [ R t + 1 + γ G t + 1 | S t = s ] = E [ R t + 1 + γ v ( S t + 1 ) | S t = s ] v ( s ) = E [ R t + 1 + γ v ( S t + 1 ) | S t = s ] = E [ R t + 1 | S t = s ] + γ E [ v ( S t + 1 ) | S t = s ] = R s + γ ∑ s ′ ∈ S P s s ′ v ( s ′ )
<script type="math/tex; mode=display" id="MathJax-Element-89"> \begin{aligned} v(s) &= E[ G_t | S_t =s]\\ & =E[R_{t+1}+\gamma R_{t+2} + \gamma ^2 R_{t+3} + \cdots | S_t = s]\\ & =E[R_{t+1}+\gamma (R_{t+2} + \gamma R_{t+3} + \cdots) | S_t = s]\\ & =E[R_{t+1}+\gamma G_{t+1} | S_t = s]\\ & =E[R_{t+1}+\gamma v(S_{t+1}) | S_t = s]\\ \\ v(s) &= E[R_{t+1}+\gamma v(S_{t+1}) | S_t = s]\\ &= E[R_{t+1} | S_t = s]+\gamma E[v(S_{t+1}) | S_t = s]\\ & = R_s + \gamma \sum_{s' \in S} P_{ss'}v(s')\\ \end{aligned} </script>

将上述式子改写成矩阵形式：

v=R+γPv⎡⎣⎢⎢v(1)⋮v(n)⎤⎦⎥⎥=⎡⎣⎢⎢R1⋮Rn⎤⎦⎥⎥+⎡⎣⎢⎢P11⋮Pn1⋯⋱⋯P1n⋮Pnn⎤⎦⎥⎥⎡⎣⎢⎢v(1)⋮v(n)⎤⎦⎥⎥ v = R + γ P v [ v ( 1 ) ⋮ v ( n ) ] = [ R 1 ⋮ R n ] + [ P 11 ⋯ P 1 n ⋮ ⋱ ⋮ P n 1 ⋯ P n n ] [ v ( 1 ) ⋮ v ( n ) ]
<script type="math/tex; mode=display" id="MathJax-Element-90"> \bf v = R + \gamma Pv \\ \begin{bmatrix} v(1) \\ \vdots \\v(n) \end{bmatrix}= \begin{bmatrix} R_1\\ \vdots \\R_n \end{bmatrix}+ \begin{bmatrix} P_{11}& \cdots & P_{1n} \\ \vdots & \ddots & \vdots \\P_{n1} & \cdots &P_{nn} \end{bmatrix} \begin{bmatrix} v(1) \\ \vdots \\v(n) \end{bmatrix} </script>

这是一个线性方程组，结合线性代数的知识可以直接求解（如果满足要求的话）：

v=(I−γP)−1R v = ( I − γ P ) − 1 R
<script type="math/tex; mode=display" id="MathJax-Element-91">\bf v = (I - \gamma P)^{-1}R</script>

对于小的MRP问题，可以直接使用上述式子求解。但对于大型的问题，则需要使用迭代的方法来进行求解。如：
-动态规划法
-蒙特卡罗法
-时间差分学习法

马尔科夫决策过程

定义

一个马尔科夫决策过程（MDP）是一个带决策的马尔科夫奖励过程，是一个其中任意状态具备马尔科夫性的环境。

马尔科夫决策过程可以使用一个元组 <S,A,P,R,γ> < S , A , P , R , γ > <script type="math/tex" id="MathJax-Element-92"></script>表示，其中：
S S <script type="math/tex" id="MathJax-Element-93">S</script>表示一个有限的状态组，
A <script type="math/tex" id="MathJax-Element-94">A</script>是一个有限的行为组，
P P <script type="math/tex" id="MathJax-Element-95">P</script>是状态转移概率矩阵， R <script type="math/tex" id="MathJax-Element-96">R</script>是回报函数;

Pass′=P[St+1=s′|St=s,At=a] P s s ′ a = P [ S t + 1 = s ′ | S t = s , A t = a ]
<script type="math/tex; mode=display" id="MathJax-Element-97">P_{ss'}^a = P[S_{t+1} = s' | S_t = s,A_t = a]</script> γ γ <script type="math/tex" id="MathJax-Element-98">\gamma</script>是衰减因子， γ∈[0,1] γ ∈ [ 0 , 1 ] <script type="math/tex" id="MathJax-Element-99">\gamma \in [0 ,1]</script>。

一个马尔科夫简单的例子如下：
马尔科夫决策过程

策略

一个策略 π π <script type="math/tex" id="MathJax-Element-100">\pi</script>是给定状态下关于行为的概率分布：

π(a|s)=P[At=a|St=s] π ( a | s ) = P [ A t = a | S t = s ]
<script type="math/tex; mode=display" id="MathJax-Element-101">\pi (a|s) = P[ A_t = a | S_t = s]</script>

-一个策略完全定义了agent的行为。
-MDP策略取决于当前的状态，非历史状态。
-策略是固定的，不是随时间变化的。

对于给定的一个MDP M=<S,A,P,R,γ> M =< S , A , P , R , γ > <script type="math/tex" id="MathJax-Element-102"> M = </script>和对应的策略 π π <script type="math/tex" id="MathJax-Element-103">\pi </script>，其状态序列 S1,S2,⋯ S 1 , S 2 , ⋯ <script type="math/tex" id="MathJax-Element-104">S_1,S_2,\cdots</script>是一个马尔科夫过程 <S,Pπ> < S , P π > <script type="math/tex" id="MathJax-Element-105"> </script>；状态及回报序列 S1,R2,S2,⋯ S 1 , R 2 , S 2 , ⋯ <script type="math/tex" id="MathJax-Element-106">S_1,R_2,S_2,\cdots</script>是一个马尔科夫奖励过程 <S,Pπ,Rπ,γ> < S , P π , R π , γ > <script type="math/tex" id="MathJax-Element-107"> </script>。

Pπss′=∑a∈Aπ(a|s)Pass′Rπs=∑a∈Aπ(a|s)Ras P s s ′ π = ∑ a ∈ A π ( a | s ) P s s ′ a R s π = ∑ a ∈ A π ( a | s ) R s a
<script type="math/tex; mode=display" id="MathJax-Element-108"> P_{ss'}^{\pi} = \sum_{a\in A}\pi(a|s)P_{ss'}^{a}\\ R_{s}^{\pi} = \sum_{a\in A}\pi(a|s)R_{s}^{a} </script>

相应地，状态价值函数可以定义为：

vπ(s)=Eπ[Gt|St=s]=Eπ[Rt+1+γvπ(St+1)|St=s] v π ( s ) = E π [ G t | S t = s ] = E π [ R t + 1 + γ v π ( S t + 1 ) | S t = s ]
<script type="math/tex; mode=display" id="MathJax-Element-109">v_{\pi}(s) = E_{\pi}[G_t | S_t = s] = E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s]</script>

另外，可以新定义行为价值函数：

qπ(s,a)=Eπ[Gt|St=s,At=a]=Eπ[Rt+1+γqπ(St+1,At+1)|St=s,At=a] q π ( s , a ) = E π [ G t | S t = s , A t = a ] = E π [ R t + 1 + γ q π ( S t + 1 , A t + 1 ) | S t = s , A t = a ]
<script type="math/tex; mode=display" id="MathJax-Element-110">q_{\pi}(s,a) = E_{\pi}[G_t | S_t = s, A_t = a] =E_{\pi}[R_{t+1} + \gamma q_{\pi}(S_{t+1},A_{t+1}) | S_t = s, A_t = a ] </script>

贝尔曼方程

qπ(s,a)=Ras+γ∑s′∈SPass′vπ(s′)=Ras+γ∑s′∈SPass′∑a′∈Aπ(a′|s′)qπ(s′,a′) q π ( s , a ) = R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) = R s a + γ ∑ s ′ ∈ S P s s ′ a ∑ a ′ ∈ A π ( a ′ | s ′ ) q π ( s ′ , a ′ )
<script type="math/tex; mode=display" id="MathJax-Element-111">\begin{aligned} q_{\pi}(s,a) &=R_s^a +\gamma \sum_{s'\in S}P_{ss'}^a v_{\pi}(s')\\ & = R_s^a +\gamma \sum_{s'\in S}P_{ss'}^a \sum_{a'\in A} \pi(a'|s')q_{\pi}(s',a')\\ \end{aligned}</script>

贝尔曼行为价值函数

vπ(s)=Eπ[Rt+1+γvπ(St+1)|St=s]=∑a∈Aπ(a|s)qπ(s,a)=∑a∈Aπ(a|s)(Ras+γ∑s′∈SPass′vπ(s′)) v π ( s ) = E π [ R t + 1 + γ v π ( S t + 1 ) | S t = s ] = ∑ a ∈ A π ( a | s ) q π ( s , a ) = ∑ a ∈ A π ( a | s ) ( R s a + γ ∑ s ′ ∈ S P s s ′ a v π ( s ′ ) )
<script type="math/tex; mode=display" id="MathJax-Element-112">\begin{aligned} v_{\pi}(s) &= E_{\pi}[R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s]\\ & = \sum_{a \in A} \pi (a | s) q_{\pi}(s,a)\\ & = \sum_{a \in A} \pi (a | s) \left( R_s^a +\gamma \sum_{s'\in S}P_{ss'}^a v_{\pi}(s') \right) \end{aligned}</script> 贝尔曼状态价值函数

改写为矩阵形式则有：

vπ=Rπ+γPπvπvπ=(I−γPπ)−1Rπ v π = R π + γ P π v π v π = ( I − γ P π ) − 1 R π
<script type="math/tex; mode=display" id="MathJax-Element-113"> v_{\pi} = R^{\pi} + \gamma P^{\pi}v_{\pi} \\ v_{\pi} = (I - \gamma P^{\pi})^{-1} R^{\pi} </script>

最优价值函数

最优状态价值函数

v∗(s)=maxπvπ(s) v ∗ ( s ) = max π v π ( s )
<script type="math/tex; mode=display" id="MathJax-Element-114">v_*(s) = \max _{\pi} v_{\pi}(s)</script>

最优行为价值函数

q∗(s,a)=maxπqπ(s,a) q ∗ ( s , a ) = max π q π ( s , a )
<script type="math/tex; mode=display" id="MathJax-Element-115">q_*(s,a) = \max_{\pi} q_{\pi} (s,a)</script>

最优价值函数指出了在马尔科夫决策过程中可能的最好决策结果，当我们知道最优结果时则称这个马尔科夫决策过程（MDP）是已解（solved）的。

最优策略

定义一种偏序:

如果对于任意的 s s <script type="math/tex" id="MathJax-Element-116">s</script>有 v π ( s ) ≥ v π ′ ( s ) <script type="math/tex" id="MathJax-Element-117">v_{\pi}(s) \ge v_{\pi '}(s)</script>,那么 π≥π′ π ≥ π ′ <script type="math/tex" id="MathJax-Element-118">\pi \ge \pi '</script>.

定理:

对于任意的MDP:
存在一个最优的策略 π∗ π ∗ <script type="math/tex" id="MathJax-Element-119">\pi_*</script>使得对于任意的 π π <script type="math/tex" id="MathJax-Element-120">\pi</script>有 π∗≥π π ∗ ≥ π <script type="math/tex" id="MathJax-Element-121">\pi _*\ge \pi </script>;
所有的最优策略对应最优状态价值函数，即： vπ∗(s)=v∗(s) v π ∗ ( s ) = v ∗ ( s ) <script type="math/tex" id="MathJax-Element-122">v_{\pi_*}(s) = v_*(s)</script>
所有的最优策略对应最优行为价值函数，即： qπ∗(s,a)=q∗(s,a) q π ∗ ( s , a ) = q ∗ ( s , a ) <script type="math/tex" id="MathJax-Element-123">q_{\pi_*}(s,a) = q_*(s,a)</script>

最优策略的寻找可以通过最大化 q∗(s,a) q ∗ ( s , a ) <script type="math/tex" id="MathJax-Element-124">q_*(s,a)</script>:

π∗(a|s)={1if  a=argmaxa∈Aq∗(s,a)0o.w. π ∗ ( a | s ) = { 1 i f     a = arg ⁡ max a ∈ A q ∗ ( s , a ) 0 o . w .
<script type="math/tex; mode=display" id="MathJax-Element-125"> \pi_*(a|s) = \left \{ \begin{aligned} &1 \qquad if \ \ a = \underset {a\in A}{\arg \max} q_*(s,a) \cr &0 \qquad o.w.\cr \end{aligned} \right. </script>

对于任意的MDP过程，总是存在一个确定的最优策略；一旦知道 q∗(s,a) q ∗ ( s , a ) <script type="math/tex" id="MathJax-Element-126">q_*(s,a)</script>则可以直接得到最优策略。

贝尔曼最优方程

v∗(s)=maxaRas+γ∑s′∈SPass′v∗(s′)q∗(s)=Ras+γ∑s′∈SPss′maxa′q∗(s′,a′) v ∗ ( s ) = max a R s a + γ ∑ s ′ ∈ S P s s ′ a v ∗ ( s ′ ) q ∗ ( s ) = R s a + γ ∑ s ′ ∈ S P s s ′ max a ′ q ∗ ( s ′ , a ′ )
<script type="math/tex; mode=display" id="MathJax-Element-127"> v_*(s) = \underset{a} \max R_s^a + \gamma \sum_{s' \in S}P_{ss'}^a v_*(s')\\ q_*(s) = R_s^a + \gamma \sum_{s' \in S}P_{ss'} \underset{a'}\max q_*(s',a') </script>

贝尔曼最优方程是非线性的，通常没有闭式解。但可以通过迭代法来求得数值解：
1、值迭代（value iteration）
2、策略迭代（policy iteration）
3、Q学习
4、Sarsa

References
[1]UCL Course on RL
[2]强化学习入门 第一讲 MDP

# 机器学习
Logo
魔乐社区

魔乐社区（Modelers.cn) 是一个中立、公益的人工智能社区，提供人工智能工具、模型、数据的托管、展示与应用协同服务，为人工智能开发及爱好者搭建开放的学习交流平台。社区通过理事会方式运作，由全产业链共同建设、共同运营、共同享有，推动国产AI生态繁荣发展。

更多推荐

cover

全家桶集齐！Qwen3.5四款小模型上线魔乐社区，附昇腾全套实践教程

avatar 魔乐社区

Pont - 搭建前后端之桥：高效、灵活的接口管理工具

Pont 是一款强大的数据服务层解决方案，它能够帮助开发者快速搭建前后端之间的桥梁，实现接口的高效管理和代码自动生成。无论是新手还是有经验的开发者，都能通过 Pont 轻松处理接口文档、生成类型安全的 API 代码，从而显著提升开发效率。[![Pont 工具标志](https://raw.gitcode.com/gh_mirrors/po/pont/raw/3f1b7d4bbba3fd2dda

avatar 魔乐社区

如何快速上手 hvac：HashiCorp Vault Python 客户端零基础入门指南

**hvac** 是 HashiCorp Vault 的 Python 3.X 客户端库，专为开发者提供简单高效的 Vault 交互方式。无论你是需要管理密钥、配置身份验证，还是实现安全的秘密数据存储，hvac 都能帮助你轻松搞定 Vault 的各项操作。本文将带你零基础快速入门，从安装到基础操作，让你在几分钟内即可上手使用这个强大的工具。[![hvac 客户端 Logo](https://r

avatar 魔乐社区