非马尔可夫奖励转化为马尔可夫奖励的方法

### 非马尔可夫奖励转化为马尔可夫奖励的方法 #### 1. 引言 在决策问题中，非马尔可夫奖励（NMRDP）为基于历史行为的奖励建模提供了强大的框架。本文提出了一种将由时态逻辑LTLf指定的非马尔可夫奖励转化为马尔可夫奖励的方法，以便使用现成的MDP规划器进行求解。 #### 2. 奖励函数优化 当DFA的规模较大时，对应的编译MDP模型也会很大，这使得MDP规划器难以求解。奖励塑造是MDP中常用的技术，旨在通过转换奖励函数来改进搜索。 - **奖励塑造函数**： - 转换后的奖励函数形式为：$R'(s, a, s') = R(s, a, s') + F(s, a, s')$，其中$R$是原始奖励函数，$F$是塑造奖励函数。 - 为避免任意的塑造奖励函数误导智能体学习次优策略，引入基于势函数的塑造奖励函数：$F(s, a, s') = \gamma\rho(s') - \rho(s)$。 - 其中$\rho : S \to R$是状态$s$的势函数；$\gamma$是MDP的折扣因子；$s$是MDP的状态；$s'$是应用动作$a$后$s$的下一个状态；$a$是MDP的动作。 - 若$F(s, a, s')$选自基于势函数的塑造奖励函数，则能保证最优和近似最优策略的保留。 - **势函数分解**： - 对于编译MDP的结构，可利用DFA对应的命题来设计塑造奖励函数。势函数$\rho(s)$可分解为在状态$s$中成立的$f_q$的势函数$\beta : Prop \to R$之和，即$\rho(s) = \sum_{f_q\in s, q\in Q}\beta(f_q)$。 - 由于塑造奖励函数$F(s, a, s')$使用了两个连续的状态，需要记录前一时刻自动机命题的值。因此，为每个$f_q$增加额外的命题$prev\_f_q$，其值根据后继状态公理更新：$next(prev\_f_q) \leftrightarrow f_q$。 - 塑造奖励函数可实例化为：$F(s, a, s') = \gamma\sum_{f_q\in s, q\in Q}\beta(f_q) - \sum_{prev\_f_q\in s, q\in Q}\beta(prev\_f_q)$。 - **示例**：在扫地机器人的例子中，当$f_{q2}$或$f_{q4}$成立时，势函数$\beta$提供正奖励；当$f_{q3}$成立时，提供负奖励。通过分配势$\beta(f_{q1}) = 0$，$\beta(f_{q2}) = 50$，$\beta(f_{q3}) = -50$，$\beta(f_{q4}) = 100$，可得到奖励塑造后的奖励函数：$R' = 100\tau_{f_{q4}} + \gamma (50\tau_{f_{q2}} - 50\tau_{f_{q3}} + 100\tau_{f_{q4}}) - (50\tau_{prev\_f_{q2}} - 50\tau_{prev\_f_{q3}} + 100\tau_{prev\_f_{q4}})$。 #### 3. 实验评估 通过IPPC的MDP基准问题实验验证该方法的可行性。将马尔可夫奖励替换为TERFs，并使用不同配置的PROST作为MDP规划器。 ##### 3.1 学术咨询问题 - **问题描述**：修改IPPC基准中的学术咨询领域问题，训练智能体按正确顺序通过课程。部分课程有先修课程，通过先修课程会增加后续课程通过的概率，且部分课程为必修课程。智能体的动作是选择课程，选择后有一定概率通过。任务是在有限时间内通过所有必修课程，并在通过前通过相应的先修课程。 - 每个必修课程的非马尔可夫奖励函数由LTLf公式指定：$\phi_c = \diamond(passed(c)) \land \square(\bigwedge_{c'}(taken(c) \land prereq(c', c)) \to passed(c'))$，其中$c$是必修课程，$prereq(c', c)$表示$c'$是$c$的先修课程。定义TERF为$\{(\phi_c : 1)|c$是必修课程$\}$。 - **实验过程**： 1. **DFA转换**：将LTLf公式$\phi_c$转换为DFA。状态$q_3$是接受状态，$q_1$是初始状态，$q_2$是错误状态，正确的状态转移过程应为$q_1 \to \cdots \to q_1 \to q_3$。 2. **构建MDP**：为DFA $\phi_c$的所有状态添加三个命题$f_{c}^{q_1}$，$f_{c}^{q_2}$和$f_{c}^{q_3}$，根据编译规则得到它们的后继状态公理： - $next(f_{c}^{q_1}) \leftrightarrow f_{c}^{q_1} \land (\neg passed(c) \land \bigwedge_{c' \text{ for } prereq(c',c)} taken(c) \to passed(c'))$ - $next(f_{c}^{q_2}) \leftrightarrow (f_{c}^{q_1} \land (taken(c) \land \bigwedge_{c' \text{ for } prereq(c',c)} \neg passed(c'))) \lor f_{c}^{q_2} \lor (f_{c}^{q_3} \land (taken(c) \land \bigwedge_{c' \text{ for } prereq(c',c)} \neg passed(c')))$ - $next(f_{c}^{q_3}) \leftrightarrow (f_{c}^{q_1} \land (passed(c) \land \bigwedge_{c' \text{ for } prereq(c',c)} (taken(c) \to passed(c')))) \lor (f_{c}^{q_3} \land (\neg taken(c) \lor \bigwedge_{c' \text{ for } prereq(c',c)} passed(c')))$ 3. **奖励函数**：$R = \sum_{c \text{ 是必修课程}}\tau_{f_{c}^{q_3}}$。 4. **优化奖励函数**：为每个课程$c$增加三个命题$\{prev\_f_{c}^{q_1}, prev\_f_{c}^{q_2}, prev\_f_{c}^{q_3}\}$，通过分配势$\beta(f_{c}^{q_1}) = 2$，$\beta(f_{c}^{q_2}) = -50$，$\beta(f_{c}^{q_3}) = 50$，定义塑造奖励函数：$R' = \sum_{c \text{ 是必修课程}}\tau_{f_{c}^{q_3}} + \gamma (2\tau_{f_{c}^{q_1}} - 50\tau_{f_{c}^{q_2}} + 50\tau_{f_{c}^{q_3}}) - (2\tau_{prev\_f_{c}^{q_1}} - 50\tau_{prev\_f_{c}^{q_2}} + 50\tau_{prev\_f_{c}^{q_3}})$。 - **实验结果评估**： ，通过不同配置的PROST对多个修改后的基准问题实例进行实验。 - **成功试验次数**： | 规划器 | 实例 | IPPC 2014（无RS） | IPPC 2014（RS） | IPPC 2011（无RS） | IPPC 2011（RS） | UCTSTAR（无RS） | UCTSTAR（RS） | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | | p_10_3_6 | 30 | 30 | 30 | 30 | 30 | 30 | | | p_10_7_15 | 29 | 30 | 29 | 30 | 28 | 30 | | | p_15_4_3 | 29 | 30 | 29 | 30 | 27 | 28 | | | p_15_7_16 | 3 | 30 | 2 | 29 | 1 | 27 | | | p_20_8_14 | 2 | 26 | 2 | 28 | 0 | 27 | | | p_20_10_23 | 0 | 27 | 0 | 27 | 0 | 26 | | | p_25_8_15 | 0 | 28 | 0 | 26 | 0 | 28 | | | p_25_9_22 | 0 | 27 | 0 | 27 | 0 | 27 | | | p_30_11_19 | 0 | 26 | 0 | 28 | 0 | 27 | 从表中可以看出，对于较简单的实例，有无奖励塑造的成功试验次数都接近30；但对于复杂实例，无奖励塑造时成功率很低（接近零），而有奖励塑造时成功试验次数接近30。这表明无奖励塑造时，MDP规划器难以生成好的解决方案，缺乏指导导致规划器短视；奖励塑造能在DFA状态转换时为规划器提供指导，使规划器获得非马尔可夫奖励。 - **运行时间**： | 实例 | 规划器 | IPPC 2014（无RS） | IPPC 2014（RS） | IPPC 2011（无RS） | IPPC 2011（RS） | UCTSTAR（无RS） | UCTSTAR（RS） | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | p_10_3_6 | | 349.9 | 347.9 | 351.4 | 348.8 | 346.2 | 344.3 | | p_10_7_15 | | 290.2 | 262.2 | 292.6 | 264.7 | 277.0 | 271.4 | | p_15_4_3 | | 481.4 | 473.9 | 479.2 | 473.1 | 488.4 | 477.9 | | p_15_7_16 | | 513.4 | 468.4 | 474.0 | 465.9 | 492.3 | 471.5 | | p_20_8_14 | | 1073.6 | 1035.6 | 1077.2 | 1040.8 | 1062.7 | 1041.3 | | p_20_10_23 | | 1029.7 | 964.5 | 1039.8 | 966.9 | 1001.8 | 961.1 | | p_25_8_15 | | 2217.8 | 2152.4 | 2267.1 | 2144.8 | 2280.6 | 2155.7 | | p_25_9_22 | | 2318.0 | 2187.6 | 2389.8 | 2190.3 | 2339.6 | 2191.5 | | p_30_11_19 | | 2322.9 | 2189.7 | 2344.6 | 2192.4 | 2403.5 | 2194.4 | 从表中可知，所有实例中RS的运行时间都比No RS短，且实例复杂度越高，运行时间缩短越明显。平均而言，IPPC 2014的运行时间减少了4.97%，IPPC 2011减少了4.88%，UCTSTAR减少了3.95%。这说明奖励塑造有助于指导搜索。 - **不同方法比较**： | 实例 | 方法 | IPPC 2014（运行时间/s） | | IPPC 2014（成功试验次数） | | IPPC 2014（平均解长度） | | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | | | A1 | A2 | A1 | A2 | A1 | A2 | | p_10_3_6 | | 347.9 | 459.9 | 30 | 30 | 6.6 | 11.4 | | p_10_7_15 | | 262.2 | 366.8 | 30 | 27 | 12.7 | 13.1 | | p_15_4_3 | | 473.9 | 525.9 | 30 | 27 | 9 | 15.2 | | p_15_7_16 | | 468.4 | 798.9 | 30 | 27 | 22.1 | 25.6 | | p_20_8_14 | | 1035.6 | 1154.5 | 26 | 26 | 28.9 | 33.2 | | p_20_10_23 | | 964.5 | 1119.5 | 27 | 24 | 22.4 | 26.5 | | p_25_8_15 | | 2152.4 | 2336.4 | 28 | 25 | 35.1 | 41.89 | | p_25_9_22 | | 2187.6 | 2467.9 | 27 | 0 | 39 | × | | p_30_11_19 | | 2189.7 | 2458.1 | 26 | 0 | 43.2 | × | 与方法A2相比，方法A1不需要将每个时间步划分为三种不同模式，因此A2的搜索树更大。对于所有实例，A1的实验结果都优于A2。A1的平均运行时间比A2少178.41 s，A2的平均解长度比A1多4.17步。 #### 4. 总结 通过实验结果可知，优化奖励函数后，成功试验次数增加，运行时间减少。奖励塑造能增强MDP规划器实现非马尔可夫奖励的性能，且本文提出的方法在运行时间、成功试验次数和解的质量等指标上均优于其他方法。这种将非马尔可夫奖励转化为马尔可夫奖励的方法具有较高的可行性和有效性，未来可将该方法扩展到深度强化学习领域。 ### 非马尔可夫奖励转化为马尔可夫奖励的方法 ##### 3.2 三角形轮胎世界问题 - **问题描述**：对三角形轮胎世界领域进行修改，一辆汽车通过道路在不同类型的位置（白色或黑色）之间移动，任务是将汽车从“起点”移动到“终点”。汽车必须在黑色和白色位置之间交替移动，直到到达“终点”。每次移动都有爆胎的可能性，爆胎后需要在下一时刻修复。 - 非马尔可夫奖励由LTLf公式指定：$\phi_{car} = \square((black \land \neg goal) \to O(\neg black)) \land \square((\neg black \land \neg goal) \to O(black)) \land \diamond(goal)$，其中$black$表示汽车在黑色位置，$goal$表示汽车到达“终点”。定义TERF为$\{(\phi_{car}, 100)\}$。 - **实验过程**： 1. **DFA转换**：将$\phi_{car}$转换为对应的DFA $A_{\phi_{car}}$。 2. **构建MDP**：为$A_{\phi_{car}}$的状态$\{q_1, q_2, q_3, q_4, q_5\}$添加额外的命题$\{f_{q1}, f_{q2}, f_{q3}, f_{q4}, f_{q5}\}$，根据$A_{\phi_{car}}$定义这些命题的后继状态公理和奖励函数： - $next(f_{q1}) = false$ - $next(f_{q2}) = (f_{q1} \land \neg goal \land \neg black) \lor (f_{q3} \land \neg goal \land \neg black) \lor (f_{q4} \land \neg goal \land \neg black)$ - $next(f_{q3}) = (f_{q1} \land goal) \lor (f_{q2} \land goal \land black) \lor (f_{q4} \land goal \land \neg black)$ - $next(f_{q4}) = (f_{q1} \land \neg goal \land black) \lor (f_{q3} \land \neg goal \land black) \lor (f_{q2} \land \neg goal \land black)$ - $next(f_{q5}) = (f_{q2} \land \neg black) \lor (f_{q4} \land black) \lor (f_{q5})$ - $R_{car} = 100 \times \tau_{f_{q3}}$ 3. **优化奖励函数**：从DFA可知，$q_3$是接受状态，$q_1$是初始状态，$q_5$是错误状态，正确的状态转移过程应为$q_1 \to q_2 \to q_4 \to q_2 \to q_4 \to \cdots \to q_2 \to q_4 \to q_3$。为每个命题增加$\{prev\_f_{q1}, prev\_f_{q2}, prev\_f_{q3}\}$，通过分配势$\beta(f_{q1}) = 0$，$\beta(f_{q2}) = 500$，$\beta(f_{q3}) = 1000$，$\beta(f_{q4}) = 500$，$\beta(f_{q5}) = 0$，定义塑造奖励函数： $R'_{car} = 100 \times \tau_{f_{q3}} + \gamma (500 \times f_{q2} + 1000 \times f_{q3} + 500 \times f_{q4}) - (500 \times \tau_{prev\_f_{q2}} + 1000 \times \tau_{prev\_f_{q3}} + 500 \times \tau_{prev\_f_{q4}})$ - **实验结果评估**：使用与学术咨询问题相同的规划器，每个实例命名为$p\_L\_R$，其中$L$是位置数量，$R$是道路数量，不同实例有不同的时间范围（范围为$[10, 20]$）。 - **成功试验次数**： | 实例 | 规划器 | IPPC 2014（无RS） | IPPC 2014（RS） | IPPC 2011（无RS） | IPPC 2011（RS） | UCTSTAR（无RS） | UCTSTAR（RS） | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | p_6_8 | | 30 | 30 | 30 | 30 | 30 | 30 | | p_15_24 | | 30 | 30 | 30 | 30 | 30 | 30 | | p_28_66 | | 30 | 30 | 30 | 30 | 30 | 30 | | p_45_80 | | 0 | 30 | 0 | 30 | 0 | 30 | | p_66_160 | | 0 | 30 | 0 | 30 | 0 | 30 | 从表中可以看出，对于前三个较简单的实例，无奖励塑造时PROST也能解决；但对于后两个复杂实例，无奖励塑造时无法解决，而有奖励塑造时能成功解决。这表明奖励塑造能有效引导MDP规划器进行搜索。 - **运行时间**： | 实例 | 规划器 | IPPC 2014（无RS） | IPPC 2014（RS） | IPPC 2011（无RS） | IPPC 2011（RS） | UCTSTAR（无RS） | UCTSTAR（RS） | | ---- | ---- | ---- | ---- | ---- | ---- | ---- | ---- | | p_6_8 | | 2.21 | 2.20 | 272.65 | 273.04 | 1.62 | 2.16 | | p_15_24 | | 6.25 | 6.67 | 275.39 | 257.89 | 6.27 | 6.64 | | p_28_66 | | 108.28 | 105.68 | 459.86 | 459.62 | 106.10 | 106.35 | | p_45_80 | | 538.36 | 569.68 | 915.42 | 907.18 | 565.39 | 584.21 | | p_66_160 | | 1049.7 | 1052.74 | 1477.2 | 1440.8 | 1062.7 | 1041.3 | 从表中可知，在大部分实例中，有奖励塑造（RS）的运行时间与无奖励塑造（No RS）处于同一水平，但整体上也能看出奖励塑造对搜索的引导作用。 - **不同方法比较**： | 实例 | 方法 | IPPC 2014（运行时间/s） | | IPPC 2014（成功试验次数） | | | ---- | ---- | ---- | ---- | ---- | ---- | | | | A1 | A2 | A1 | A2 | | p_6_8 | | 2.20 | 6.28 | 30 | 30 | | p_15_24 | | 6.67 | 16.92 | 30 | 27 | | p_28_66 | | 105.68 | 108.86 | 30 | 24 | | p_45_80 | | 569.68 | 663.42 | 30 | 27 | | p_66_160 | | 1052.74 | 1382.01 | 26 | 23 | 从表中可以看出，对于所有实例，方法A1的运行时间都比方法A2短，且成功试验次数也更有优势。由于每个实例只有一个解，因此未比较解的长度。 ### 5. 整体总结与展望 - **奖励塑造的作用**：通过两个实验可以清晰地看到，奖励塑造在MDP规划中起到了至关重要的作用。在复杂的非马尔可夫奖励场景下，无奖励塑造时MDP规划器往往难以生成有效的解决方案，容易陷入盲目搜索，导致成功试验次数少、运行时间长。而奖励塑造通过设计合理的塑造奖励函数，为规划器提供了即时奖励和搜索指导，使规划器能够更好地理解状态之间的关系，更高效地找到接近最优的策略，从而显著提高了成功试验次数，缩短了运行时间。 - **方法优势**：本文提出的将非马尔可夫奖励转化为马尔可夫奖励的方法，在多个方面展现出明显优势。与其他方法相比，不需要将每个时间步划分为多种不同模式，避免了搜索树的过度增大，从而在运行时间、成功试验次数和解的质量等指标上均取得了更好的结果。这种方法不仅具有理论上的合理性，还在实际实验中得到了有效验证。 - **未来展望**：考虑到深度强化学习在处理复杂决策问题上的强大能力，未来可以将这种将非马尔可夫奖励转化为马尔可夫奖励的方法扩展到深度强化学习领域。深度强化学习结合本文的奖励转化和塑造技术，有望在更复杂、更具挑战性的实际应用场景中发挥更大的作用，例如自动驾驶、机器人控制等领域，为解决实际问题提供更有效的解决方案。 ### 实验流程总结流程图 ```mermaid graph LR classDef startend fill:#F5EBFF,stroke:#BE8FED,stroke-width:2px; classDef process fill:#E5F6FF,stroke:#73A6FF,stroke-width:2px; classDef decision fill:#FFF6CC,stroke:#FFBC52,stroke-width:2px; A([开始]):::startend --> B(选择实验问题):::process B --> C{学术咨询问题?}:::decision C -->|是| D(定义非马尔可夫奖励函数):::process C -->|否| E(三角形轮胎世界问题):::process E --> F(定义非马尔可夫奖励函数):::process D --> G(DFA转换):::process F --> G G --> H(构建MDP):::process H --> I(定义奖励函数):::process I --> J(优化奖励函数):::process J --> K(进行实验):::process K --> L(评估实验结果):::process L --> M([结束]):::startend ``` 综上所述，本文提出的方法为解决非马尔可夫奖励问题提供了一种有效的途径，通过奖励塑造增强了MDP规划器的性能，并且在实验中得到了良好的验证。未来的扩展应用有望进一步推动该领域的发展。