下载掌阅APP，畅读海量书库
立即打开
多周期优化问题在现实世界中随处可见，小到个人的学习计划，大到一个经济体的管理，还包括航班排期、新设备采购、库存管理、车辆调度和投资等问题，都属于多周期优化问题，甚至是下棋和打羽毛球这种我们日常的游戏也可以看成是多周期优化问题。这些问题通常都遵循这样一个流程：决策—信息获取—进一步决策—进一步信息获取，这一循环不断迭代，直到计划周期结束。我们把这样一类问题称为顺序决策问题。从以上的描述可以看出，顺序决策问题的建模不难，但是求解起来却是充满了挑战。
动态规划在科学研究中的多个领域都有应用。在工程和经济领域，研究的动态规划问题是基于连续状态和决策，决策变量多为地点、速度和温度等物理变量。而运筹学和人工智能领域遇到的多是离散状态和决策的动态规划问题。连续状态和决策的问题通常利用控制理论进行求解，而离散状态和决策的问题则是利用马尔可夫过程进行求解。这两种方法的思想都是通过建立迭代方程，并利用状态变量来搜集历史信息进行求解。有些高维问题，如资源分配问题，也可以用数学规划的方法来求解。大部分研究集中于确定性问题，通常利用线性规划、非线性规划，或是整数规划来求解，而那些涉及不确定因素的多周期优化问题则被称为随机规划问题。
接下来我们先介绍一下动态规划模型所包含的元素。
（1）状态变量：主要包括决策所需的所有信息，以及用来描述系统随时间推移而演变的信息。
（2）决策变量：决策/行为，也就是我们如何控制系统的整个过程。
（3）外生信息：外生信息通常在每个决策周期期初可以观察到，如产品需求、购买或出售产品的价格，同时我们需要知道系统的初始状态。
（4）转移函数：该函数决定了系统在给定第t期决策和第t期到第t+1期之间的外生信息时如何从状态 S t 演化到S t+1 。
（5）目标函数：该函数通常为计划周期内成本最小或是收益最大。
动态规划问题一般利用贝尔曼最优方程进行逆向递归求解。但面对很多实际问题时，由于问题规模较大，我们很难通过贝尔曼最优方程进行精确求解。由于问题规模大而造成的动态规划问题求解困难存在于三个方面，称为维数灾，主要包括由于问题规模扩大而导致的状态集变大和决策集变大，以及求解未来周期成本函数的期望值也变得困难。
近似动态规划方法则是解决传统动态规划算法所面临的维数灾问题的一种方法。当然，近似动态规划方法在其他领域也有广泛的应用。在动态规划模型中，如果缺少对信息过程的有效描述，则模型的转移函数未知，即使是规模不大的问题也不容易解决。例如，我们可以观察某种资产的价格变化，但却无法建立一个有效的数学模型，又或是下棋时我们可以观察对方的行为，但却无法描述他做决策的整个思维过程。这些情况下，我们就无法计算值函数的期望值。另外一个例子，假设我们试图研究一个国家的经济状况与国际货币基金贷款之间的关系，如果我们无法获取该国经济情况与贷款数量之间的关系，则无法确切知道整个系统的转移函数。同时，很多问题无法精确求解的原因就是规模较大。假设一个多技能呼叫中心可以处理有关个人电脑的一些问题，客户打电话来，通过键盘号码选择所需的服务类型，进而呼叫中心根据这一信息将客户分配到擅长这一方面问题的接线员。这就是一个随机的动态分配问题，该问题由于包括多属性资源从而状态集巨大。
近似动态规划的基本思想是随时间前向推进的算法策略，因此也被称为前向动态规划。如果我们采用传统的动态规划方法求解，则需要计算每一个状态S t 对应的值函数V t （S t ），然后从中选出使得值函数最大的行动策略a t ∈A t 。大规模的问题无法用传统的动态规划方法求解，主要因为需要对所有的状态进行计算然后比较，这在时间成本方面不切实际。与之不同的是，近似动态规划算法前向推进，从而对整个系统随时间的演化过程进行仿真。但为了达到这一目的，我们需要解决两个问题：一是随机产生一组状态样本，即系统将来可能发生的状态；二是进行决策。下面我们先来分析决策相关的问题，然后来解决随机信息的方针问题。
前面提到过在精确动态规划中，算法随时间逆向推进，对所有状态对应的值函数进行计算，并用来求解最优决策。而在前向推进的近似动态规划中，我们并没有计算值函数，因此不能精确计算得到最优决策，而需要通过近似方法进行决策。
表示值函数的近似形式。最易于理解的方式是假设
是对应每个状态的值函数近似形式，但正是由于它是近似值，我们可以选择任何形式的函数，这就导致选取合适的近似函数形式较为困难。
近似动态规划通过迭代计算近似函数
进而前向推进。假设初始近似值函数
已知（通常情况下赋值为零），
为迭代n-1次之后所得的值函数近似值，下面我们来分析第n次迭代的情况。我们从t=0及初始状态S
0
开始，决策a
0
可以通过以下公式求解。
给定决策S 0 ，算法则在状态S 0 前向推进到S 1 ，这一过程首先是采取a 0 这一行动，然后我们需要知道在t=0和t=1之间的外生信息。在t=0时刻，外生信息未知，因此是随机的。我们的策略是随机产生一组外生信息的样本，这一过程通常被称为蒙特卡洛仿真（Monte Carlo Simulation）。它是一种实践中常用的产生随机信息的方法，主要利用一种人工过程从群体中选取随机样本。举个例子，如果一种商品的价格在60～70元，服从均匀分布，我们则可以通过很多软件的随机数生成器生成一组随机价格。给定随机生成的外部信息，算法可以计算下一个访问的状态S 1 。这里有一个前提是我们知道系统的转移函数。由于我们已知每个决策周期的值函数估计值，算法可以通过进一步迭代求解a 1 。算法将一直进行迭代直到计划周期结束。由于决策过程是基于我们对值函数的估计，因此我们称之为贪婪策略。近似动态规划算法的根本是生成样本路径，它是指一个特定的外生信息序列。
近似动态规划依赖于随机变量的样本序列，而如何获取这些样本取决于问题的设置。通常情况下，获取随机样本的方法有以下3种。
（1）从现实世界中获取：有些外部信息可以直接从现实物理进程中获取。比如，我们可以利用真实的需求序列来估计平均需求，其他的变量如价格、成本、行驶时间等也都可以通过对真实世界的观察得到。
（2）计算机仿真实验：可以通过计算机对复杂过程进行仿真从而计算出一组随机变量的样本。仿真对象可以是供应链或是资产分配模型。
（3）根据已有概率分布取样：这是最为简单的一种随机取样方法，利用多数软件自带的随机数生成工具就可以从标准概率分布中生成随机样本。这样的方法可以在短时间内产生大量样本。
前向算法如果只针对一组抽样样本路径进行当然没有太大意义，因此我们需要对大量的样本路径重复进行前向算法，这也是采用值函数逼近的一个代价。在算法迭代过程中，n表示当前迭代次数，相应的ω
n
则是第n次迭代中用到的随机外生信息。在周期t，系统状态处于S
t
，通过第n-1期迭代的值函数逼近值
可以得到第n次迭代的决策
，需要指出的是
上标表示该值函数逼近值是由前n-1次迭代的信息计算所得。给定
，我们可以获得第t+1期的外生信息，系统从而进入到下一个状态
，直到计划周期结束，然后算法进入下一个迭代循环继续进行。基本的近似动态规划算法如下。
第0步：初始化
0a.对所有状态S
t
的值函数
进行初始化。
0b.选择一个初始状态
。
0c.令n=1。
第1步：选择一个样本路径ω n 。
第2步：For t=0，1，2，…，T do。
2a. 求解
设
为以上最大化问题的解。
2b.利用
对
进行更新。
2c.计算
。
第3步：令n=n+1，如果n<N，回到第一步。
除了前向推进之外，近似动态规划算法跟逆向动态规划算法很类似。虽然这一算法不需要遍历所有系统状态，但同样也面临着以下一系列新的挑战。
（1）虽然避免了遍历所有可能的系统状态，但由于需要一步转移概率矩阵，计算量同样很大。
（2）前向推进造成算法仅对访问过的状态所对应的值函数进行更新，但我们同样需要对那些未访问的状态对应的值函数进行估计。
（3）由于利用值函数逼近值来进行前向推进，算法有可能会陷入一个循环而永远无法访问那些看起来差但实际对应较好值函数值的状态。
（4）以上的基础算法具有一般性，但却未能提供一些针对具体问题结构性质的算法机制。
策略是动态规划中应用较为广泛的一个术语，其定义为：给定状态S t 的相关信息时，决定其最优决策的规则（或函数）。从以上的定义可以看出，这一概念的问题在于它可以是任何用来确定某一状态下决策的方法，所以对于不同的问题及不同的计算时间要求，需要不同的方法来确定对应的策略。因此，为了能够有效解决隶属于动态规划范畴内的各种各样的问题，我们需要对策略的种类进行划分。同时，也需要研究如何确定每种决策对应的最佳策略。通常情况下，我们可以把策略分成以下4类。
（1）近视策略：这是最基础的一类策略。这一类策略仅对当前周期的成本/收益进行最优化，并不考虑任何形式未来周期的信息。虽然简单，但是通过不断的参数调整，该方法在一些情况下也可以取得较好的效果。
（2）展望策略：比起近视策略，展望策略会利用一部分未来周期的信息，并通过对未来周期未知信息的近似从而对当前周期进行决策。
（3）策略函数逼近：这一函数直接给出对应当前状态的行动/决策，并不依赖于任何优化或是直接应用对未来周期信息的预测。
（4）值函数逼近：这一类策略也被称为贪婪策略，它主要依赖于基于当前周期策略对未来周期状态对应的值函数进行逼近。当前周期策略对未来周期的影响主要通过当前周期决策导致的未来周期状态所对应的值函数来刻画。
首先，我们简单来了解一下前两类算法的本质属性。由于它不考虑任何形式的未来周期信息，近视策略最为简单。展望策略通过对未来周期的未知信息进行逼近从而对当期决策进行最优化计算。因此，展望策略可能会有较大的计算量。针对这一问题，很多研究专注于研发更好的逼近方法，较为普遍的是对应决策前和决策后状态（Post-state Decision）的值函数逼近。
算法无论是要对值函数进行逼近还是对策略函数进行逼近，我们都需要了解以下3类逼近算法。
（1）查表法：也称表格函数，是指每一个离散状态S都对应一个离散的值函数值。
（2）有参数的表示：通常指带参数的显性解析函数，用在近似值函数或者策略函数中。
（3）无参数表示：通常指某一类较为复杂且具有一般性的函数。
接下来，我们将介绍一些主要的近似动态规划算法。首先我们将关注点放在表格法的值函数逼近算法，即对应每一个状态储存一个值函数的值，然后通过查表的方法进行求解。接下来将分别讨论这类方法中的4种算法。
（1）Q-学习算法：该方法主要针对状态集和策略集较小且不能通过数学模型来描绘系统随时间变化的问题。
（2）实时动态规划算法：该算法为基础算法的一个变形，但可以证明该算法的收敛性。
（3）近似值迭代算法：在这一算法中我们不用假设一步转移概率矩阵就可以计算。
（4）决策后状态变量的近似迭代算法：我们将首先介绍决策后状态变量的概念，然后阐述其如何简化算法计算。
①Q-学习算法。
Q-学习算法是强化学习领域最古老的算法之一，由其变量Q（s，a）而得名。其中，Q（s，a）为在状态s下采取行动a时的值函数逼近值。SARSA基于Q-学习算法进行了优化，二者不仅是近似动态规划的入门级算法，更为我们了解探索的重要作用提供了一个很好的机制。
Q-学习算法：
是Q（s，a）在n次迭代之后的统计估计值。假设系统处于状态S
n
，通过求解
，进而可以得到所需采取的行动a
n
。在第n次迭代中，算法利用第n-1次迭代中的估计值
。Q-学习算法的一个主要特点是在通过近似贝尔曼最优方程计算行动时，算法既不需要计算期望值也不需要对未来下游状态对应的值函数进行估计。许多物理系统十分复杂以至于很难用数学模型对其进行描述，但是可以直接观察系统的行为。这一类应用来源于实际运作场景，即生产模型中我们可以观察到系统外生结果和状态转移，而不是利用数学公式对其进行刻画。动态规划中有3个方面的数学模型。在工程界，第一种模型指的是转移函数，无模型动态规划指的是没有显性转移函数的问题。在这一类问题中，我们做出决策然后需要从物理过程中观察决策的结果。第二种模型指的是外生信息过程。对于这一类过程并没有一个概率分布可以对其结果进行描述。这将无法计算一步转移概率矩阵，甚至由于无法知道每种结果对应的概率而无法进行仿真。在这种情况下，我们假设拥有一个外生结果产生过程。第三种模型为成本/贡献函数。例如，在一个系统中，人通过决策来最大化一个未知的效用函数，我们可以通过一个系统来观察这个人的行为，同时推测在该状态下他将采取什么行动。
在强化学习领域，模型通常指一步转移概率矩阵，计算一步转移概率矩阵不仅意味着转移函数和外生信息概率分布已知，同时也需要状态集离散且数量小。选择行动a
n
，假设可以观察到贡献C＾（S
n
，a
n
）及下一个状态S
n+1
，然后可以计算在状态S
n
采取行动a
n
的值函数值
，进而对Q因子进行更新
，其中α为0，1上的步长。常用是固定步长或是衰退法则，如
。给定一系列Q因子，可以计算在状态s的逼近值
。与一般的近似动态规划算法作比较可以看出，在近似动态规划算法中，我们需要计算行动a
t
对应的未来下游状态的期望函数值，从而找到
。而Q-学习算法则主要依赖于对外生过程的观察，并不需要转移函数S
M
。
如果利用近似贝尔曼最优方程来选择行动可能算法并不一定能找到最优解，问题在于
可能会低估一些状态-行动所对应的值。而算法中的行动并不能使我们访问这些状态，从而忽略了那些可以得到更好结果的行动。因此，需要通过探索更多状态来找到那些看起来并不好但却有可能使系统转移到更好状态的状态。一种有效的方法是使用∈-贪婪策略，该策略按∈的概率在策略集中随机选择一个策略，按1-∈的概率用近似贝尔曼最优方程选择策略。通过这种方法我们可以探索状态集中更多的不经常被访问的状态。∈-贪婪策略简单且易于理解，同时也保证算法可以无限次访问每个状态。当然，对于状态集和策略集较大的问题Q-学习算法就不适用了，但它的价值在于可以在没有模型的情况下求解问题。
SARSA的命名来源于该算法的具体实施过程：首先系统处于状态s，选择行动a，之后观测到收益r，进而转移到下一个状态s′，从而选择行动a′，序列s，a，r，s′，a′则构成了该算法的名字。SARSA是一种针对一个固定策略对应的值函数值进行学习的算法，该算法需要确保所有行动都被无限次的检验。根据算法的构造，所有的行动会按照一个由策略确定的频率被检验。同时，从状态S n 到S n+1 ，我们需要保证按照策略所决定的正确分布来对状态进行抽样。但该算法不是要寻找最优（或是更好）的策略，而只是对一个策略对应的值函数进行估计。尽管如此，该算法依然在策略迭代算法中扮演着重要的角色。
Q-学习算法和SARSA算法为我们介绍离线算法和在线算法做了很好的铺垫。SARSA算法在给定状态S n ，选择行动a n 时和到达未来状态选择行动a′=A π （S {n+1} ）时用的是同一个策略A π （S）。只要我们的策略可以确保所有的行动可以被无限次选择，就能保证Q-因子会收敛到正确的状态对应的值函数值，并且根据策略A π （S）选择行动。同时，沿着状态S n 到S n+1 =S M （S n ，A π （S），W n+1 ）的轨迹，我们可以确保按照策略所决定的比例对状态进行抽样。与之相对的，Q-学习算法则按照∈-贪婪算法来选择行动，而在下游状态时，利用max a {Q n-1 （S n+1 ，a）}来选择之后的行动。也就是说，使用一种策略来选择哪一个行动需要评估，而使用另外一种策略来选择未来周期的行动。
在近似动态规划中，我们经常会选择当前状态下我们认为最好的行动，一旦某个策略看起来最好，我们将对其进行评估；但如果算法这么做，就可能困在一小部分看起来不错的状态，而忽略了那些看起来不好的状态，最终可能得不到很好的结果。要解决这个问题，我们可以引入类似∈-贪婪算法等的探索策略，但这也意味着我们利用一种不同的策略来强行进行探索，而却对另外一种不同的策略进行评估。用来决定选择哪种行动，并使系统状态转移到下一个状态的策略被称为行为策略，这是用来刻画一个物理系统如何表现的。如果在一个线上系统中，行为策略是用来描述系统的行动，而在仿真实验中，我们则是用这种策略来控制状态抽样的过程。在这种情况下，该策略被称为抽样策略。在强化学习领域，可以决定看起来最好的行动的策略称为靶向策略，或是更形象的被称为学习策略。虽然我们应用抽样策略来确保能够访问每个状态足够多的次数，但最终的目的是改进靶向策略。当学习策略和抽样策略一致时（就像SARSA算法一样），该算法为在线策略学习，而当学习策略和抽样策略不同时，我们称之为离线策略学习。
在近似动态规划和强化学习中的一个重要问题是关于在线策略学习和离线策略学习的选择。在线策略学习并不能确保抽样过程使得状态集中的所有状态有足够的访问次数进而对其对应的值函数进行准确估计。而离线策略学习可能会影响我们对学习策略对应的值函数值的学习效果。
②实时动态规划。实时动态规划基于一个重要的假设，即一步转移概率可以计算，但是算法对这一假设进行了微小调整使得我们可以确保算法最终收敛于最优策略。我们先从较为容易理解的确定版的实时动态规划——A
*
算法讲起。A
*
算法是一类最短路算法。我们来考虑一个确定性的网络，边（i，j）对应确定性的贡献c（i，j）。我们从起点q出发到达终点r，目标是最大化总贡献。假设，已知v是对从i到r的贡献的乐观估计值。当前在点i，选择边（i，j）使得c
ij
+v
j
最大，如果（i，j
*
）是最好的选择，则
，并重复这一过程。这一算法从起点q开始，每当到达r时重新从q开始。如果一开始我们对每个点的估计都是乐观的，就可以保证每次迭代我们的估计值后，改进的估计值也是乐观的。如果在点i并没有选择边（i，j），即使v（j）并不正确，我们也可以确保选择的是更好的一条路。
实时动态规划是随机版的A
*
算法，假设V（s）是对状态s的值函数的一个乐观估计值。如果采取行动a，假设从s到s′的转移概率P（s′|s，a）已知。在状态S
n
，选择a
n
，则通过求解
即可得到a
n
为最优行动，更新
，而其他状态对应的估计值不变，下一个状态为S
n
=S
M
（S
n
，a
n
，W
n+1
），具体算法如下所示。
第0步：初始化。
0a.对所有状态s的值函数
进行初始化。
0b.选择一个初始状态S 1 。
0c.令n=1。
第1步：选择一个样本路径ω n 。
第2步：For t=0，1，2，…，T do。
2a. 求解
设a n 为以上最大化问题的解。
2b.利用
对
进行更新。
2c.计算S n =S M （S n ，a n ，W（ω n ））。
第3步：令n=n+1，如果n<N，回到第一步。
就像A * 算法，如果V n-1 （s）是乐观估计，就可以确保V n （s）也是乐观估计。只要所有的估计值都是乐观的，算法就可以探索所有看起来最好的行动。乐观估计可以确保如果算法没有选择这一行动，则我们就可以安全的忽略这一行动。而如果选择了一个行动就是因为下游状态对应的值是乐观的，从而这些值都得到正确的更新。但为了得到收敛的保证，算法也需要付出一些代价。首先，算法需要计算一步转移概率矩阵进而精确计算期望值。其次，应用乐观估计就要对每个状态进行多次访问，这对于状态集巨大的问题是一个挑战。
③近似值迭代算法。与实时动态规划相比，近似值迭代算法并不需要一步转移概率就可以计算。在这一假设下，一种策略是在每次迭代时随机生成一个外生信息的结果样本，P
n
（ω）为这一样本结果的概率。如果算法选取N个观测值，则
，进而我们可以对期望值进行近似
及状态S
n
对应的值函数估计
，最后对其进行更新
。以上方法是在近似动态规划中常用的一种操作，被称为平滑、线性过滤，或是随机近似。有时选取确定步长（0或1），或是确定的公式（如
），又或是自适应的方法。以上这些方法的目的都是利用带噪数据
的观测值来近似实际观测值概率分布的均值。
（s
n
）是n次迭代后状态s
n
对应的值函数的最佳估计值。平滑这一步骤主要是出于我们对期望值的近似方法所导致的
的随机性，具体算法如下所示。与之前提到的算法相比，该算法已完全不需要对状态集所有状态进行循环。理论上来讲，该算法可以解决状态集任意大的问题。
第0步：初始化。
0a.对所有状态s的值函数
进行初始化。
0b.选择一个初始状态
。
0c.令n=1。
第1步：选择在t和t+1之间所产生信息结果的一个随机样本
。
第2步：求解。
设a n 为以上最大化问题的解。
第3步：利用
对
进行更新。
第4步：计算S n+1 =S M （S n ，a n ，W（ω n ））。
第5步：令n=n+1，如果n<N，回到第一步。
④决策后状态变量。
对于多数实际问题来说，有一种简单且易于理解的方法可以避免近似期望值这个繁杂的步骤——决策后状态变量。它是在系统进行决策后但在新的外生信息产生前的一个系统状态。在多数问题中，决策后状态都比决策前状态简单。事实上，决策后状态为我们求解决策变量为向量形式的问题提供了有效的方法。
对于许多问题而言，可以将状态变量中受决策影响的部分和受外生信息影响的部分分开。例如，在库存问题中，转移函数为
，分成两个部分为
和
。其中，
刻画的是订货a
t
这一行动的影响，而R
t+1
则是刻画了观测到需求
的影响。因此，一般来讲，我们可以把原来的转移函数
分成两部分
和
，其中S
t
是决策前的系统状态，
为决策后状态变量。最为直观的例子就是决策树了。从近似贝尔曼最优方程中我们可以看到，在决策点的信息为决策前状态，而在结果点的信息为决策后变量。转移函数
刻画的是从决策点（决策前状态）到结果点（决策后状态）的变化，而转移函数
刻画的是从结果点到决策点的变化。决定是否采用决策后状态变量的方法比较简单，如果值函数的期望值EV
t+1
（S
t+1
）很容易计算，则应选择决策前状态变量，相反则要考虑是否可以识别出一个较好的决策后状态变量。如果可以利用问题的结构特点精确计算期望值，则可以得到比蒙特卡洛仿真更为可靠的结果。
假设我们找到了决策后变量
处的值函数值
，算法将迭代进行。假设算法处于第n次迭代，在时刻t系统处于状态
，优化问题可以写成
。最为关键的是我们发现这一问题其实是一个确定性问题。我们并不需要直接计算期望值甚至是对其进行近似。这对于大规模问题而言是至关重要的。接下来要对值函数近似值进行更新，
为状态
值函数值的一个抽样，这样就可以利用以下方法进行更新
。这是我们之前利用决策前状态变量的更新公式。如果换成决策后状态则为
。对应的贝尔曼方程为
，从这里可以看到利用决策后状态变量我们就避免了对期望值的精确计算或是近似计算，具体算法如下所示。
第0步：初始化。
0a.对所有值函数
，t∈T进行初始化。
0b.令n=1。
0c.选择一个初始状态
。
第1步：选择一个样本路径ω n 。
第2步：Do for t=0，1，2，…，T。
2a. 求解。
设
为以上最大化问题的解。
2b.如果t>0，利用
对
进行更新。
2c.计算决策后状态
及下一个决策前状态
。
第3步：令n=n+1，如果n<N，回到第一步。
第4步：返回值函数
。
利用决策后状态变量进行前向动态规划更加简洁有效是由于它不用对优化问题中的期望值进行近似计算。同时，这一算法也为我们提供了一个有效的工具。由于决策方程可以直接观测到值函数
（而不是通过期望值的近似计算间接得到），我们可以对值函数的结构进行控制。这一特性对于那些单期问题为特殊结构的整数规划、复杂的线性或非线性规划尤为有效。该算法可以为大规模解决实际问题提供高质量的模型。前向算法利用了所有经典的仿真工具，这可以帮助我们对问题中方方面面的细节进行有效的仿真。而算法能够提供高质量决策的一个关键就是可以构造能够准确刻画当前决策对未来影响的值函数近似形式。对于那些具有高维决策变量的优化问题，我们需要通过数学规划的方法进行求解。而求解的关键就是能够识别出那些能够帮助我们更好地进行值函数近似构造的性质。
经典的动态规划通常假设值函数的表示形式是离散的，即对应每一个状态s∈S，我们需要估计一个值函数值。前向动态规划可以避免对所有系统状态进行循环，但并不能完全解决状态集的维数灾问题。前向动态规划算法主要关注实际访问过的状态，但同时也需要对那些可能会访问的状态有一定的了解。近似规划算法中基本上所有大规模的问题都关注如何通过一小部分参数对值函数进行近似计算。为达成目的，我们需要利用蒙特卡洛抽样，而这一方法的主要问题是统计误差。在实际中，对值函数进行近似计算需要了解问题的基本结构。聚类算法是对离散变量问题进行值函数逼近的一种主要方法。在动态规划发展的早期，聚类算法被看作是利用一小部分状态进行有效近似的一个方法。但当时存在的一个问题是需要针对聚类的状态集求解整个问题。而在近似动态规划中，我们仅需要利用聚类的方法对值函数进行近似计算。而对于转移函数、贡献函数和约束的计算，我们仍然保留了所有系统状态。这一点非常有价值。在近似动态规划领域，聚类提供了一个降低统计误差的机制，因此，虽然聚类可能会引入结构性误差，但却可以通过提高统计鲁棒性而使模型更加准确。对于那些状态的维度是分类而且非熟知的问题，由于没有其他的结构性质需要探索，聚类方法是极为有效的。
同时，近似策略的设计还面临两个方面的挑战。首先，我们需要利用问题的结构特性来对值函数进行近似计算，同时确保近似形式可以简化单期问题的求解，即单期问题可以在一个合理的时间内找到最优解。如果需要通过遍历所有决策而进行选择，这当然不是问题，但如果a t 是一个向量，这就很难能达到简化计算的目的。如果单期问题是线性或非线性规划，则不会考虑用表格法来进行值函数的近似计算。如果单期问题是连续可导且凹的，非凹值函数就不会是一个好的选择。如果单期问题是一个离散的排期问题且可以通过搜索启发式算法求解，这样表格法就可以适用。确定好值函数的结构之后，我们需要确定一个更新策略。值函数本质上来说是利用经典统计方法进行更新的统计模型，而最方便的方法是通过迭代的方式进行更新，利用多个参数和大量观测值的回归方法并不适用。
近似动态规划可以从4个方面来解读：根据所求解的问题不同，近似动态规划可以帮助改进可观测的实体过程；它是求解复杂动态规划问题的一种有效算法；它使得经典的仿真过程更加智能；它是大规模数学规划问题的一种分解技术。
近似动态规划作为强化学习的一个分支，一直以来都是通过对状态-行动对进行学习而提高求解质量的一种方法。从这个角度来看，如果一个实体过程可以观测状态之间的转移，在当前状态下，根据策略选择行动，然后学习求得对应的收益，这样就可以利用多种求解的方法来对策略进行更新和改进。
在学界，近似动态规划主要用来求解那些存在维数灾困难的动态规划问题，而对求解贝尔曼最优方程的挑战，当状态集很大时，我们需要克服计算值函数的困难。同时，当决策集很大且无法遍历，甚至是计算期望值也很困难时，我们都需要近似动态规划来帮忙。
近似动态规划的另一个作用就是可以看作是具有更加智能决策法则的经典仿真器。所有的近似动态算法都包括两个主要部分：优化，即进行决策；仿真，即刻画随机信息的影响。从这个角度来看，近似动态规划就是一个优化的仿真器。由转移函数所刻画的状态变量及其所在的实体过程的复杂性实际上是没有限制的。但我们仅将其限制在值函数逼近的复杂度之内。如果系统状态过于复杂，我们则需要设计可以利用最重要特性的有效的近似动态规划方法。在实际应用中最为重要的一个方面是我们并不简化那些用于计算转移函数的状态变量。
探索-利用困境是近似动态规划中一个重要的问题。它们就像跷跷板的两端此消彼长，需要很好的权衡才能发挥最佳效果。探索是指通过访问系统状态而获取更多的关于该状态的信息，并不考虑该状态所对应的值函数是否是最好的。利用则是根据对贡献函数和值函数的最佳估计，以及现有的所有信息做出最好的决策。探索主要通过两种途径：一种方法是在更新当前状态的值函数后，我们可以随机选择下一个访问状态（不论下一个状态是否已经访问过）；另一种方法是随机选择一个行为（即使不是最好的）从而使系统进入下一个随机的状态。后一种方法的价值在于它可以将我们搜索的状态限定于从当前状态可以合理到达的范围内，避免出现不可行的状态。但对于决策集和状态集中的变量都是多维向量形式的问题，随机抽样的状态和行动的选择帮助不大。
通过探索来获取状态信息和利用值函数来访问那些看起来收益较好的状态之间的权衡问题是近似动态规划中至今未能完全解决的一个难题。如果只是根据当前对值函数的估计来访问那些看起来收益最大的状态（纯利用策略），我们将面临最终收敛于局部最优解的风险。有些方法可以帮助我们跳出这一困境，但付出的代价就是算法收敛速度慢。只有通过利用具体问题的结构特点才能设计出收敛速度相对合理的算法。