马尔可夫决策过程
在老虎机问题中，无论智能代理采取什么行动，之后要解决的问题都是一样的。也就是寻找最好的老虎机。但现实生活中的问题是不同的。例如，在围棋游戏中，智能代理落子后，棋盘上的棋子排列会发生变化（对手落子会进一步改变棋盘上的棋子排列）。智能代理采取的不同行动导致棋局每时每刻都在变化。智能代理需要考虑到棋局的转变，下出最佳的一手。--环境变化，需要考虑不同的状态。
接下来探讨的是情况随智能代理的行动而变化的问题。一些这样的问题被定义为马尔可夫决策过程（MDP）。
首先介绍在MDP中出现的术语，并用数学式表示它们。
然后，在阐明MDP的目标的基础上通过实际介绍一个简单的MDP问题来了解实现这些目标的过程。
智能代理的目标是实现奖励总和最大化。
以上就是对MDP的简单介绍。接下来我们将用数学式来描述MDP。
环境和智能代理的数学表示
MDP通过数学式来表示智能代理、环境以及二者之间的互动。要做到这一点，需要用数学式来表达以下3个要素。
• 状态迁移：状态如何迁移。
• 奖励：如何给予奖励。
• 策略：智能代理如何决定行动。
状态迁移（输入：s_t,a_t；输出：s_t+1）
当智能代理选择向左移动的行动，结果表示它“总是”向左移动（左图）。
如果智能代理选择了向左移动的行动，那么它将以0.9的概率向左移动，以0.1的概率留在原地（右图）。这种随机行动可能是地板打滑或智能代理的内部机制(如电机)，不能正常工作所导致的。
状态迁移不需要过去的信息——此前处于什么状态以及执行了哪些行动。这个特性被称为马尔可夫性（Markovproperty）。
MDP通过假设马尔可夫性的存在来模拟状态迁移和奖励。
奖励函数（输入：s_t,a_t,s_t+1，输出：r_t）
智能代理的策略（输入：s_t，输出：a_t）
策略的关键在于它使得智能代理仅根据当前状态来决定其行动。之所以说只基于当前状态就足够了，是因为环境的迁移是符合马尔可夫性的。即关于环境的所有必要信息都在当前状态中。因
此，智能代理只需基于当前状态即可决定其行动。
智能代理的策略可以根据其当前状态来决定。智能代理的行动可以是确定性的，也可以是随机性的。确定性的策略在某个状态下总是采取固定的行动，如图2-8中的左图所示。
MDP的目标
状态价值函数（收益的期望值）
下面引入一个新术语一收益（return）
智能代理的目标是使这种收益最大化。
这里有一点需要注意，那就是智能代理和环境的行动可能是“随机性”的。智能代理可能随机地决定行动，状态也可能随机迁移。在这种情况下，最终获得的收益将呈现随机的特点。
每次所处的状态和策略
最优策略和最优价值函数
MDP的具体问题
这段代码没有进行无穷无尽的计算，而是使用for语句进行了近似计算（100次）。结果大约是-8,与理论值几乎相同。
小结
智能代理有策略。
对于环境：有状态迁移概率(或状态迁移函数)和奖励函数。
环境和智能代理之间会互动：策略决定当前状态的行动（可以是确定也可以是随机的），智能体根据做出的行动进行状态迁移（可能由于内部故障等原因造成新状态的随机性，形成概率分布），最后根据新的状态智能体获得奖励。
MDP的目标是在这样一个框架内找到最优策略。最优策略是指在所有状态下其状态价值函数的值大于或等于任何其他策略。
对 “有两个方格的网格世界”的强化学习问题来说，我们列出了所有可能的策略，并手动计算了每个策略的状态价值函数。最后我们找到了其中最好的策略一最优策略。不过本章中使用的方法只对有两个方格的网格世界这种设定简单的强化学习问题有效。
贝尔曼方程
应用场景
上面的假设仅仅是确定性的策略，使得我们可以穷尽所有的策略，计算该策略下的奖励。但若采取随机性策略，是无法计算每个状态的状态价值函数的：
此时需要应用贝尔曼方程，对状态价值函数进一步推导，使其变得可以求解。
状态价值函数的贝尔曼方程推导
状态价值函数与收益有关：
在研究式3.1的结构时，首先将t+1代入式3.1中的t中：
（也就是说，当前状态的收益与下一状态相关。）
下面将式3.3代入状态价值函数的定义式中。状态价值函数是收益的期望值，其数学式的定义如下所示。
这是根据期望的计算公式推导的：
推导第二项：
要求的项：处于当前状态的下一状态期望收益期望值
推导后的项：处于下一状态的条件下的收益期望值
关键在于：
也就是说有如下关系：
随机性策略的状态价值函数计算
上面我们推导了状态价值函数的贝尔曼方程，继续回到刚才的问题，这次假设智能代理是随机移动的。也就是说，它有50%的机会向右移动，50%的机会向左移动
观察图3-9,回溯线形图有两个分支，其中一个分支是以0.5的概率选择行动Left,并且总是迁移到状态Z1。在这种情况下得到的奖励是-1。折现率y被设定为0.9。因此，式3.8中选择Left的项可以表示为下面的式子。
图3-9中的另一个分支是以0.5的概率选择行动Right,之后会迁移到状态L2,奖励为1。用数学式可以表示为如下形式。
汇总：
求状态L2下的贝尔曼方程。也像刚才一样：
贝尔曼方程能够将无限的计算转换为有限的联立方程。尽管这次的问题中存在随机性行动，我们还是使用贝尔曼方程求出了状态价值函数。
行动价值函数的贝尔曼方程推导
本节将介绍一个新的函数--行动价值函数(action-value function)与状态价值函数一样，行动价值函数也是出现在许多强化学习理论中的重要函数。我们之前已经用状态价值函数推导出了贝尔曼方程。本节会先给出行动价值函数的定义式，然后再推导行动价值函数的贝尔曼方程。
它也是用于表示收益的期望值，但是它将行动也纳入了条件中，与状态价值函数一样，也将策略作为参数。
在状态价值函数的回溯线形图中，行动a是根据策略选择的。而在Q函数的回溯线形图中，行动a可以自由选择（可以选择计算行动a1/a2/a3的行动价值函数：
/
/
）。这是状态价值函数和Q函数之间的唯一区别（Q函数只需考虑状态迁移的随机性）
接下来推导行动价值函数（Q函数）的贝尔曼方程。首先将Q函数展开为如下形式。
因此此时我们有两个贝尔曼方程：
贝尔曼最优方程
贝尔曼方程是对所有策略（确定/随机）成立的方程。但我们最终想要求出的是最优策略。最优策略是使所有状态下的状态价值函数最大化的策略。最优策略当然也满足贝尔曼方程。
此外，利用策略是“最优”的特性，我们可以用一种更简单的形式来表示贝尔曼方程。本节将介绍对最优策略成立的方程，即贝尔曼最优方程(Bellman optimality equation)
状态价值函数的贝尔曼最优方程
行动价值函数的贝尔曼最优方程
在MDP中，至少存在一个确定性的最优策略。确定性策略是指在给定状态下总是选择特定行动的策略。可能存在一个以上的最优策略，但它们的价值函数的值相同。
应用贝尔曼最优方程（最优策略的状态价值函数计算）
如何求解：
但我们最终想知道的是最优策略。接下来思考一下最优策略
得到最优策略
小结
强化学习的最终目标是得到最优策略。我们在本章中还学习了贝尔曼最优方程。贝尔曼最优方程是对最优策略成立的特殊的贝尔曼方程。只要知道最优策略的价值函数，就很容易得到最优策略
下一节将介绍动态规划（借鉴贝尔曼方程德强化学习算法实现）。
