Algorithm for Inverse Reinforcement Learning

摘要：这篇文章解决了马尔可夫决策过程中的逆强化学习问题，也就是，从一个给定被观察的、最优的行为中提取出reward function。IRL也许可以帮助apprenticeship learning获得熟练的行为，以及确定由自然系统优化的reward function。我们首先刻画给定最优策略的reward function的集合，然后我们推导出三个IRL的算法。前面两个算法解决知道entire policy的情形；我们处理在有限状态空间中的表格型reward function和潜在无线状态空间上reward function的线性函数逼近。第三个算法处理更加实际的情形，即策略只能通过一个有限的可被观察的trajectory的集合来被知道。在所有的情形中，一个关键的问题就是degeneracy(退化)——存在大量的reward function导致被观察到的策略是最优的。为了消除degeneracy，我们建议使用一些自然启发式方法来尝试选择一个能够最大限度地将观察到的策略与其他次优策略区分开来的reward function。这导致了IRL问题的一个可被高效解决的线性规划建模。我们在简单的离散/有限和连续/无线的状态问题上验证了我们的算法。

Introduction

逆强化学习问题可以被不正式地刻画成如下：

Given

1. 在各种情形下，一个agent随时间变化的行为的评估（measurements）
2. 如果需要的话，measurements of the sensory inputs to that agent
3. 如果有的话，一个环境模型

Determine 正在被优化的reward function

我们可以确定这个问题的motivation的两个来源。第一个是强化学习和其相关的方法有潜力作为动物和人类学习的计算模型。这些得到行为研究和神经生理学支持的模型被证明强化学习发生在蜜蜂觅食和夜莺发声中。然而，这个文献假设reward function是固定和已知的——例如，蜜蜂觅食模型假设每朵花的reward是花蜜含量的简单饱和函数（saturating function）。很明显的是，在检查动物和人类行为时，我们必须将reward function视为一个需要实验研究的未知的东西。这在多属性的reward function上是尤其正确的。例如，考虑到蜜蜂可能会根据飞行距离、时间以及风和捕食者的风险来衡量花蜜摄入量。这很难知道如何先验的确定这些属性的相对权重。相似的考虑也同样发生在人类的经济行为身上。因此，逆强化学习是生物理论，经济理论和其他领域的一个基础问题。

第二个motivation来自于在一个指定的领域构建一个能够成功行动的智能体的任务。一个agent设计者（或者是agent它本身）可能只有一个关于能够生成理想行为的reward function的初步的想法，所以直接的强化学习可能不再适用。（例如，考虑自动驾驶的任务）一个学习的信息的来源是其他“专家”agent的行为，正如用在模仿学习（imitation learning）和学徒学习（apprenticeship learning）中的一样。在这种设定下，通常假设观察的目的就是为了学习一个策略，比如说，一个从状态映射到行为的直接表示（direct representation）。相反，我们提出重新获得专家的reward function并使用它来生成理想的行为。我们建议reward function通常提供更为简洁的行为描述。毕竟，强化学习的整个领域都是建立在这样一个假设之上，即reward function而不是策略是对人物最简洁、鲁棒和可转移的定义。 因此，在某些领域，这看起来好像逆强化学习提供了一个学徒学习（apprenticeship learning）的高效形式。

据我们所知，这个计算任务还没有被计算机科学、控制理论、心理学或者生物学深入的研究过。最接近的一个工作是在经济学中，其中对多属性效用评估的任务进行了深入的研究——也就是说，一个人在做出决定时实际上如何结合每个可用选择的各种属性。这个理论被很好地发展了，并且应用广泛。然而，该领域仅研究采取单一行动且结果立刻可见的一次性决策。序列化的情形第一次被Sargent考虑，他通过检查公司一段时间内的雇佣行为来确定劳动力的有效雇佣成本。在过去的几十年中，计量经济学中马尔可夫决策过程的结构化估计得到了迅速的发展。一些基本的想法延续到我们的设置中。IRL也在控制理论中简短出现过：在20世纪60年代早期，Kalman提出了具有二次成本的确定性线性系统的目标函数的恢复问题。这在最近被当作一个半正定程序来解决了。

在这篇文章中，我们从有限状态的马尔可夫决策过程（Markov decision processes, MDPs）开始，在机器学习社区更熟悉的环境中解决IRL问题。Section 2给出了MDPs和IRL问题的正式定义；我们集中在模型是已知的和给出了完整策略的初始设置的情况下。Section 3刻画了给定最优策略的所有reward function的集合。我们模拟这个集合包含很多退化（degenerate）的solution，例如，包括在任何地方都是0的reward function。我们通过启发式的尝试选择能够最大程度的区分观察到的策略和其他次优策略的reward function来解决这个难点。这个在离散的情况下，可以通过使用线性规划高效地解决。Section 4解决很大的或者无限状态空间的情形，在这种情况下，显式的、表格型的reward function是不可行的。我们证明了如果合适的reward function被表示为任意的、固定的基函数的线性组合，那么IRL问题仍然处于线性规划的分类中而且可以被高效的解决。Section 5处理更加实际的问题，那就是策略只能通过一个有限的可被观察的轨迹的集合来知道，对于这个，我们提出了一个简单的迭代算法。在Section 6, 这三个我们提出的算法被应用在一些简单的样例中，包含离散和连续的随机导航问题，以及“mountain-car”问题。在所有的情形中，我们都能够恢复一个能够很好地解释被观察到的行为的reward function。最后，Section 7总结了我们的发现和描述了未来工作的一个方向。

Notation and Problem Formulation

在这个section中，我们介绍了马尔可夫决策过程的一些符号，定义和基本理论。随后，我们定义了我们将解决的IRL问题。

Markov Decision Processes

A (finite) MDP is a tuple ( S , A , { P s a , γ , R } ) (S,A,\{P_{sa}, \gamma, R\}) (S,A,{Psa​,γ,R}), where

• S S S is a finite set of N N N states.
• A = { a 1 , . . . , a k } A=\{a_1, ...,a_k\} A={a1​,...,ak​} is a set of k k k actions.
• P s a ( . ) P_{sa}(.) Psa​(.) are the state transition probabilities upon taking action a a a in state s s s.
• γ ∈ [ 0 , 1 ) \gamma \in [0,1) γ∈[0,1) is the discount factor.
• R : S → R R:S\rightarrow \mathbb{R} R:S→R is the reinforcement function bounded in absolute value by R m a x R_{max} Rmax​.

为了说明的简洁性，我们将reward写成 R ( s ) R(s) R(s)而不是 R ( s , a ) R(s,a) R(s,a)。

一个策略（policy）被定义为任意的一个映射 π : S → A \pi:S\rightarrow A π:S→A， 并且对于一个策略 π \pi π的价值函数，在任意状态 s 1 s_1 s1​的评估形式为：

V π ( s 1 ) = E [ R ( s 1 ) + γ R ( s 2 ) + γ 2 R ( s 3 ) + . . . ∣ π ] V^{\pi}(s_1)=E[R(s_1)+\gamma R(s_2)+\gamma^2 R(s_3)+...|\pi] Vπ(s1​)=E[R(s1​)+γR(s2​)+γ2R(s3​)+...∣π]

其中期望是在状态序列 ( s 1 , s 2 , . . . ) (s_1, s_2,...) (s1​,s2​,...)的分布上计算的，而状态序列是从状态 s 1 s_1 s1​开始执行策略 π \pi π获得的。我们同样也定义了Q-function，如下所示：

Q π ( s , a ) = R ( s ) + γ E s ′ ∼ P s a ( . ) [ V π ( s ′ ) ] Q^{\pi}(s,a)=R(s)+\gamma E_{s'\sim P_{sa}(.)}[V^{\pi}(s')] Qπ(s,a)=R(s)+γEs′∼Psa​(.)​[Vπ(s′)]

（其中这个符号 s ′ ∼ P s a ( . ) s'\sim P_{sa}(.) s′∼Psa​(.)表示期望是关于根据 P s a ( . ) P_{sa}(.) Psa​(.)分布的 s ′ s' s′的期望。）最优的价值函数是 V ∗ ( s ) = sup ⁡ π V π ( s ) V^{*}(s)=\sup_{\pi} V^{\pi}(s) V∗(s)=supπ​Vπ(s)，并且最优的Q-function 是 Q ∗ ( s , a ) = sup ⁡ π Q π ( s , a ) Q^{*}(s,a)=\sup_{\pi}Q^{\pi}(s,a) Q∗(s,a)=supπ​Qπ(s,a)。

对于离散、有限的空间，所有这些函数都可以表示为以状态为索引的向量，向量我们采用粗体表示法。更精确的是，将有限状态空间固定为从1到 N N N的枚举。这个reward可以被写成一个 N N N维向量** R R R**, 其中第 i i i个元素就是马尔可夫过程的第 i i i个状态。相似的， V π V^{\pi} Vπ是一个向量，它的第 i i i个元素就是价值函数使用策略 π \pi π对第 i i i个状态的评估。对于每一个动作 a a a，我们也让 P a P_a Pa​表示一个 N × N N\times N N×N的矩阵，其中元素 ( i , j ) (i,j) (i,j)表示从状态 i i i采取动作 a a a转移到状态 j j j的概率。最后，我们让符号 ≺ \prec ≺和 ⪯ \preceq ⪯表示严格和不严格的向量不等性，比如， x ≺ y x\prec y x≺y当且仅当 ∀ i , x i < y i \forall i, x_i <y_i ∀i,xi​<yi​。

标准强化学习的目标是找出一个策略 π \pi π使得 V π ( s ) V^{\pi}(s) Vπ(s)最大化。可以被证明的是存在至少一个最优策略 π ∗ \pi^* π∗使得 V π ( s ) V^{\pi}(s) Vπ(s)当 π = π ∗ \pi = \pi^* π=π∗时对所有的状态 s ∈ S s \in S s∈S同时取得最优。

Basic Properties of MDPs

为了解决IRL问题，我们需要两个关于MDP的经典结果。

定理一：(Bellman Equations) 给定一个马尔可夫决策过程 M = { S , A , { P s a } , γ , R } M=\{S,A, \{P_{sa}\},\gamma, R \} M={S,A,{Psa​},γ,R}和一个策略 π : S → A \pi:S \rightarrow A π:S→A。那么，对于所有的 s ∈ S , a ∈ A s \in S, a\in A s∈S,a∈A， V π V^\pi Vπ和 Q π Q^{\pi} Qπ符合

V π ( s ) = R ( s ) + γ ∑ s ′ P s π ( s ) ( s ′ ) V π ( s ′ ) (1) V^{\pi}(s)=R(s)+\gamma \sum_{s'}P_{s\pi(s)}(s')V^{\pi}(s') \tag{1} Vπ(s)=R(s)+γs′∑​Psπ(s)​(s′)Vπ(s′)(1)

Q π ( s , a ) = R ( s ) + γ ∑ s ′ P s a ( s ′ ) V π ( s ′ ) (2) Q^{\pi}(s,a)=R(s)+\gamma \sum_{s'}P_{sa}(s')V^{\pi}(s') \tag{2} Qπ(s,a)=R(s)+γs′∑​Psa​(s′)Vπ(s′)(2)

定理二：(Bellman Optimality) 给定一个马尔可夫决策过程 M = { S , A , { P s a } , γ , R } M=\{S,A, \{P_{sa}\},\gamma, R \} M={S,A,{Psa​},γ,R}和一个策略 π : S → A \pi:S \rightarrow A π:S→A。那么 π \pi π是一个 M M M的最优策略当且仅当对于所有的 s ∈ S s\in S s∈S

π ( s ) ∈ arg ⁡ max ⁡ a ∈ A Q π ( s , a ) (3) \pi(s) \in \arg \max_{a\in A}Q^{\pi}(s,a) \tag{3} π(s)∈arga∈Amax​Qπ(s,a)(3)

Inverse Reinforcement Learning

逆强化学习问题是找到一个能够解释观察到行为的reward function。我们从一个状态空间是有限的、模型是已知的、完整的策略是可被观察的简单例子开始。更准确的是，我们给定一个有限的状态空间 S S S，一个含有 k k k个动作的集合 A = { a 1 , . . . , a k } A=\{a_1, ...,a_k\} A={a1​,...,ak​}， 转移概率 { P s a } \{P_{sa}\} {Psa​}，一个衰减因子 γ \gamma γ和一个策略 π \pi π，我们希望能够找到一个可能的reward function R R R的集合使得策略 π \pi π是马尔可夫决策过程 { S , A , { P s a } , γ , R } \{S,A, \{P_{sa}\},\gamma, R \} {S,A,{Psa​},γ,R}中的最优策略。（然后我们可能希望在这个集合中识别满足额外标准的函数）通过在必要时重命名动作，我们将不失一般性地假设 π ( s ) ≡ a 1 \pi(s)\equiv a_1 π(s)≡a1​。这个技巧只是用来简化我们的符号表示。

IRL in Finite State Spaces

在这个Section，我们简单的刻画了一个能够让给定策略是最优的reward function的集合。我们随后证明了这个集合包含很多退化（degenerate）的solutions，并且提出了一个简单的启发式方法来移除这些退化 (degeneracy)，导致了IRL问题的线性规划解决方案。

Characterization of the Solution Set

我们刻画这个solution集合的主要结果如下所示：

定理三： 给定一个有限状态空间 S S S, 一个动作集合 A = { a 1 , . . . , a k } A=\{a_1,...,a_k\} A={a1​,...,ak​}，转移概率矩阵 { P a } \{\mathbf{P}_a\} {Pa​}和一个衰减因子 γ ∈ ( 0 , 1 ) \gamma\in (0,1) γ∈(0,1)。给定 π ( s ) ≡ a 1 \pi (s)\equiv a_1 π(s)≡a1​, 这个策略 π \pi π是最优的当且仅当对所有的动作 a = a 2 , . . , a k a=a_2,..,a_k a=a2​,..,ak​， reward R R R满足

( P a 1 − P ( a ) ) ( I − γ P a 1 ) − 1 R ⪰ 0 (4) (\mathbf{P}_{a_1}-\mathbf{P}(a))(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \succeq 0 \tag{4} (Pa1​​−P(a))(I−γPa1​​)−1R⪰0(4)

证明： Since π ( s ) ≡ a 1 \pi(s)\equiv a_1 π(s)≡a1​, Equation (1) may be writtern V π = R + γ P a 1 V π \mathbf{V}^{\pi}=\mathbf{R}+\gamma \mathbf{P}_{a_1}\mathbf{V}^{\pi} Vπ=R+γPa1​​Vπ. Thus,

V π = ( I − γ P a 1 ) − 1 R (5) \mathbf{V}^{\pi} = (\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \tag{5} Vπ=(I−γPa1​​)−1R(5)

Substituting Equation (2) into (3) from Therorem 2. we see that π ≡ a 1 \pi \equiv a_1 π≡a1​ is optimal if and ponly if

a 1 ≡ π ( s ) ∈ arg ⁡ max ⁡ a ∈ A ∑ s ′ P s a ( s ′ ) V π ( s ′ )   ∀ s ∈ S a_1 \equiv \pi(s) \in \arg \max_{a \in A} \sum_{s'}P_{sa}(s')V^{\pi}(s')\ \forall s\in S a1​≡π(s)∈arga∈Amax​s′∑​Psa​(s′)Vπ(s′) ∀s∈S
⇔ ∑ s ′ P s a 1 ( s ′ ) V π ( s ′ ) ≥ ∑ s ′ P s a ( s ′ ) V π ( s ′ )   ∀ s ∈ S , a ∈ A \Leftrightarrow \sum_{s'}P_{sa_1}(s')V^{\pi}(s') \geq \sum_{s'}P_{sa}(s')V^{\pi}(s')\ \forall s\in S, a\in A ⇔s′∑​Psa1​​(s′)Vπ(s′)≥s′∑​Psa​(s′)Vπ(s′) ∀s∈S,a∈A

⇔ P a 1 V π ⪰ P a V π   ∀ a ∈ A ∖ a 1 \Leftrightarrow \mathbf{P}_{a_1}\mathbf{V}^{\pi} \succeq \mathbf{P}_a\mathbf{V}^\pi\ \forall a \in A\setminus a_1 ⇔Pa1​​Vπ⪰Pa​Vπ ∀a∈A∖a1​

⇔ P a 1 ( I − γ P a 1 ) − 1 R ⪰ P a ( I − γ P a 1 ) − 1 R \Leftrightarrow \mathbf{P}_{a_1}(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \succeq \mathbf{P}_{a}(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} ⇔Pa1​​(I−γPa1​​)−1R⪰Pa​(I−γPa1​​)−1R

where the last implication in this derivation used Equation (5). This cp,pletes the proof.

注： Here, I − γ P a 1 \mathbf{I}-\gamma \mathbf{P}_{a_1} I−γPa1​​ is always invertible. To see this, first note that P a 1 \mathbf{P}_{a_1} Pa1​​, being a transition matrix, has all eigenvalues in the unit circle in the complex plane. Since γ < 1 \gamma < 1 γ<1, the implies that matrix γ P a 1 \gamma \mathbf{P}_{a_1} γPa1​​ has all eigenvalues in the interior of the unit circle (and in particular that 1 is not an eigenvalue). This means I − γ P a 1 \mathbf{I}-\gamma \mathbf{P}_{a_1} I−γPa1​​ has no zero eigenvalues, and is thus not sigular.

Remark: 使用非常相似的证明方法，很容易可以证明（本质上是用严格的不等式替换上面证明中的所有不等式）条件 ( P a 1 − P ( a ) ) ( I − γ P a 1 ) − 1 R ≻ 0 (\mathbf{P}_{a_1}-\mathbf{P}(a))(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}\mathbf{R} \succ 0 (Pa1​​−P(a))(I−γPa1​​)−1R≻0是结论 π ≡ a 1 \pi \equiv a_1 π≡a1​成为唯一最优策略的必要充分条件。

对于有限状态的马尔可夫决策过程，这个结论描述了所有的reinforcement function集合都是逆强化学习问题的solution。然而，我们也立刻看到了两个问题：首先， R = 0 \mathbf{R}=0 R=0（甚至任何其他的常数向量）都是一个solution——如果无论我们采取什么动作reward都相同，那么任何策略包括 π ≡ a 1 \pi \equiv a_1 π≡a1​都是最优的。要求 π \pi π是唯一的最优策略将缓解这个问题，但是并不完全令人满意，因为通常一些任意接近0的reward vector仍然是solution。第二个，对于大多数的马尔可夫决策过程，这看起来好像仍然还是有很多对于 R \mathbf{R} R的选择符合criteria (4)。我们怎样从这么多reinforcement functions中选择一个？这个答案不会从原始的IRL问题的陈述中找到，但是在下一个Section，我们描述了一些可以对这两个问题的solution提供建议的自然标准 (natural criteria)。

LP Formulation and Penalty Terms

显然，线性规划可以被用来找满足方程 (4)约束的可行点，但是正如前面Section讨论的那样，其中一些点可能不如其他点“有意义”，因此，我们希望能够找到一些方式在这些满足方程 (4)的solution中进行选择。在很大程度上我们选择了在这个Section中的建议，因为它们可以被整合到线性规划中，但是尽管如此，他们看起来还是很自然。

一个自然方式来选择 R R R首先要求它能够使策略 π \pi π最优（因此能够解决IRL问题），此外，更加倾向于使任何单步偏离 π \pi π的成本尽可能高的solution。因此，对于所有能够满足 (4)的函数 R R R (and ∣ R ( s ) ∣ ≤ R max ⁡ ∀ s |R(s)| \leq R_{\max} \forall s ∣R(s)∣≤Rmax​∀s)，我们可能会选着使得下式最大的那个

∑ s ∈ S ( Q π ( s , a 1 ) − max ⁡ a ∈ A ∖ a 1 Q π ( s , a ) ) (6) \sum_{s\in S}(Q^{\pi}(s,a_1)-\max_{a\in A \setminus a_1}Q^{\pi}(s,a)) \tag{6} s∈S∑​(Qπ(s,a1​)−a∈A∖a1​max​Qπ(s,a))(6)

换句话说，我们寻求最好动作和第二好动作的差的和的最大化。（其他标准，比如说 ∑ s ∈ S ∑ a ∈ A ∖ a 1 Q π ( s , a 1 ) − Q π ( s , a ) \sum_{s\in S}\sum_{a\in A\setminus a_1} Q^{\pi}(s,a_1)-Q^{\pi}(s,a) ∑s∈S​∑a∈A∖a1​​Qπ(s,a1​)−Qπ(s,a)也是可能的，但是为了具体化，让我们暂时停留在（6）上）

此外，如果我们相信，在所有其他条件相同的情况下，以小reward为主的solution会更简单，因此更可取。我们可以选择性地在目标函数中添加一个类似权重衰减的惩罚项，比如 − λ ∣ ∣ R ∣ ∣ 1 -\lambda ||R||_1 −λ∣∣R∣∣1​， 其中 λ \lambda λ是一个可调整的惩罚系数，用来平衡想要小的reinforcement和最大化 (6)这个两个目标。使用比如 l 1 l_1 l1​惩罚项的副作用是：对于足够大的 λ \lambda λ， R R R 只有在少数几个状态是非零项，这个与我们的想法“简单的reward function”相一致。此外，虽然在许多应用中手动调整惩罚系数是常见的作法，这可以被看出（假设solution在 λ = 0 \lambda =0 λ=0处没有退化 (degenerate)）随着$\lambda 增 加 ， 在 某 点 增加，在某点 增加，在某点\lambda_0 会 发 生 p h a s e 的 转 移 ， 使 得 对 于 会发生phase的转移，使得对于 会发生phase的转移，使得对于\lambda < \lambda_0 , 最 优 , 最优 ,最优R 远 离 0 ， 对 于 远离0，对于 远离0，对于\lambda >\lambda_0, R=0 。 因 此 ， 如 果 我 们 想 自 动 的 选 择 。因此，如果我们想自动的选择 。因此，如果我们想自动的选择\lambda ， ， ，\lambda =\lambda_0^- （ p h a s e 刚 刚 发 生 转 移 之 前 的 值 ， 可 能 可 以 通 过 对 （phase刚刚发生转移之前的值，可能可以通过对 （phase刚刚发生转移之前的值，可能可以通过对\lambda 的 二 分 查 找 得 到 ） 将 会 是 一 个 吸 引 人 的 选 择 ， 因 为 它 给 出 了 一 个 最 简 单 的 的二分查找得到）将会是一个吸引人的选择，因为它给出了一个最简单的 的二分查找得到）将会是一个吸引人的选择，因为它给出了一个最简单的R （ 最 大 的 惩 罚 系 数 ） 使 得 （最大的惩罚系数）使得 （最大的惩罚系数）使得R 不 会 在 任 何 地 方 都 为 0 （ 而 且 可 以 使 得 不会在任何地方都为0（而且可以使得 不会在任何地方都为0（而且可以使得R 至 少 能 够 部 分 地 解 释 为 什 么 至少能够部分地解释为什么 至少能够部分地解释为什么\pi$是最优的）。

将这些放在一起，我们的优化问题变为：

maximize ∑ i = 1 N min ⁡ a ∈ { a 2 , . . . , a k } { ( P a 1 ( i ) − P a ( i ) ) − ( I − γ P a 1 ) − 1 R − λ ∣ ∣ R ∣ ∣ 1 } \sum_{i=1}^{N} \min_{a\in\{a_2,...,a_k\}}\{(\mathbf{P}_{a_1}(i)-\mathbf{P}_{a}(i))-(\mathbf{I}-\gamma \mathbf{P}_{a_1})^{-1}R-\lambda ||R||_1\} i=1∑N​a∈{a2​,...,ak​}min​{(Pa1​​(i)−Pa​(i))−(I−γPa1​​)−1R−λ∣∣R∣∣1​}

s . t .   ( P a 1 − P a ) ( I − γ P a 1 ) − 1 R ⪰ 0   ∀ s ∈ A ∖ a 1 s.t.\ (\mathbf{P}_{a_1}-\mathbf{P}_{a})(\mathbf{I}-\gamma\mathbf{P}_{a_1})^{-1}R \succeq 0\ \forall s \in A\setminus a_1 s.t. (Pa1​​−Pa​)(I−γPa1​​)−1R⪰0 ∀s∈A∖a1​

∣ R ∣ ≤ R max ⁡ ,   i = 1 , . . . , N |\mathbf{R}|\leq R_{\max},\ i=1,...,N ∣R∣≤Rmax​, i=1,...,N

其中 P a ( i ) \mathbf{P}_a(i) Pa​(i)表示矩阵 P a \mathbf{P}_a Pa​的第 i i i行。清楚地是，这个可以被很简单的建模成一个线性规划问题而且被很高效的解决。

Linear Function Approximation in Large State Spaces