马尔可夫决策过程（MDP)简介
下一个状态 S t + 1 S_{t+1} St+1是从概率分布P中得到的，该概率分布P取决于整个历史，因此我们需要考虑从 s 0 s_0 s0开始到t时刻的状态。马尔可夫是具有马尔可夫性质的随机过程
- 定义
P [ S t + 1 ∣ S t ] = P [ S t + 1 ∣ S 1 , . . . , S t ] \Bbb{P}[S_{t+1}|S_t]=\Bbb{P}[S_{t+1}|S_1,...,S_t] P[St+1∣St]=P[St+1∣S1,...,St]
“The future is independent of the past given the present”
也就是说，未来只与现在有关，与过去无关，根据现在可以推衍未来（过去无可挽回，未来可以知晓）。如此问题就简化了，得到 S t + 1 S_{t+1} St+1，只需要知道 S t S_{t} St
- 性质
- 状态从历史（history）中捕获了所有相关信息 S = f ( H ) S=f(H) S=f(H)
- 当状态已知的时候，可以抛开历史不管
- 也就是说，当前状态是未来的充分统计量
举例：马尔可夫性质意味着t时刻的状态（和动作）包含了足够的信息来完全确定t+1时刻的下一个状态转移概率。斐波那契序列，可以用动态规划的方式让式子 s t + 1 = s t − 1 + s t s_{t+1}=s_{t-1}+s_{t} st+1=st−1+st成立。
- MDP五元组
- S S S是状态的集合
- A A A是动作的集合
- P s a P_{sa} Psa是状态转移函数
- γ ∈ [ 0 , 1 ] \gamma \in [0,1] γ∈[0,1]是对未来奖励的折扣因子
- R R R是奖励，有时候仅仅与状态有关系
动态过程
如上图所示，MDP的动态过程如下：
- 从状态 s 0 s_0 s0开始
- 智能体（Agent）选择一个动作 a 0 ∈ A a_0\in A a0∈A
- 智能体获得奖励 R ( s 0 , a 0 ) R(s_0,a_0) R(s0,a0)
- MDP随机转移到下一个状态 s 1 s_1 s1~ P s 0 a 0 P_{s_0a_0} Ps0a0
上述过程会不断循环执行，直至终止状态 S t S_t St出现
贝尔曼方程
贝尔曼方程
贝尔曼方程是对价值函数的一个简化，可将价值函数分解为及时奖励和衰减后的未来奖励之和
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 + γ V ( s ) ∣ S t = s ] V(s)=\Bbb{E}_\pi[G_{t}|S_t=s]{\kern 135pt}\\ =\Bbb{E}_\pi[R_{t+1}+\gamma R_{t+2}+\gamma ^2R_{t+3}+...|S_t=s]{\kern 4pt}\\ =\Bbb{E}_\pi[R_{t+1}+\gamma (R_{t+2}+\gamma R_{t+3}+...)|S_t=s]{\kern 0pt}\\ =\Bbb{E}_\pi[R_{t+1}+\gamma V(s)|S_t=s]{\kern 65pt} 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+γV(s)∣St=s]
同理，动作价值函数可以表示为：
Q ( s ) = E [ R t + 1 + γ V ( s ) ∣ S t = s , A t = a ] = E [ R t + 1 + γ E a ∼ π Q ( S t + 1 , a ) ∣ S t = s , A t = a ] Q(s)=\Bbb{E}[R_{t+1}+\gamma V(s)|S_t=s,A_t=a]{\kern 64pt}\\ =\Bbb{E}[R_{t+1}+\gamma \Bbb{E}_{a\sim\pi}Q(S_{t+1,a})|S_t=s,A_t=a]{\kern 0pt} Q(s)=E[Rt+1+γV(s)∣St=s,At=a]=E[Rt+1+γEa∼πQ(St+1,a)∣St=s,At=a]
贝尔曼期望方程
P s a P_{sa} Psa是状态转移概率，有其它的写法 P s π ( s ) P_{s\pi(s)} Psπ(s)、 P s s ′ a P_{ss'}^a Pss′a,表示在当前的状态s，经过动作a后，转移到其它状态的概率分布。
V π ( s ) = E π [ R t + 1 + γ V π ( s ) ∣ S t = s ] = R ( s ) + γ ∑ s ′ ∈ S P s s ′ a V π ( s ′ ) V_\pi(s)=\Bbb{E}_\pi[R_{t+1}+\gamma V_\pi(s)|S_t=s]{\kern 18pt}\\ =R(s)+\gamma \sum_{s'\in S}P_{ss'}^aV_\pi(s'){\kern 0pt} Vπ(s)=Eπ[Rt+1+γVπ(s)∣St=s]=R(s)+γs′∈S∑Pss′aVπ(s′)
同理
Q π ( s ) = R ( s , a ) + γ ∑ s ′ ∈ S P s s ′ a ∑ a ′ ∈ A π ( a ′ ∣ s ′ ) Q π ( s ′ , a ′ ) Q_\pi(s)=R(s,a)+\gamma \sum_{s'\in S}P_{ss'}^a\sum_{a'\in A}\pi(a'|s')Q_\pi(s',a'){\kern 0pt} Qπ(s)=R(s,a)+γs′∈S∑Pss′aa′∈A∑π(a′∣s′)Qπ(s′,a′)
贝尔曼最优方程
对状态𝑠来说的最优价值函数是所有策略可获得的最大可能折扣奖励的和
V ∗ ( s ) = m a x π V π ( s ) V ∗ ( s ) = R ( s ) + m a x a ∈ A γ ∑ s ′ ∈ S P s s ′ a V ∗ ( s ′ ) V_*(s)=\underset {\pi}{max}V_{\pi}(s){\kern 0pt}\\ V_*(s)=R(s)+\underset {a\in A}{max}\gamma \sum_{s'\in S}P_{ss'}^aV_*(s'){\kern 0pt} V∗(s)=πmaxVπ(s)V∗(s)=R(s)+a∈Amaxγs′∈S∑Pss′aV∗(s′)
同理
Q ∗ ( s , a ) = m a x π Q π ( s , a ) Q ∗ ( s , a ) = R ( s , a ) + γ ∑ s ′ ∈ S P s s ′ a m a x a ′ ∈ A Q ∗ ( s ′ , a ′ ) Q_*(s,a)=\underset {\pi}{max}Q_{\pi}(s,a)\\ Q_*(s,a)=R(s,a)+\gamma \sum_{s'\in S}P_{ss'}^a\underset {a'\in A}{max}Q_*(s',a'){\kern 0pt} Q∗(s,a)=πmaxQπ(s,a)Q∗(s,a)=R(s,a)+γs′∈S∑Pss′aa′∈AmaxQ∗(s′,a′)
