随机环境中多智能体协调的社会法则：α-鲁棒性的形式化与验证
核心概要
该工作把社会法则从确定性的目标驱动设定扩展到随机的、奖励驱动的多智能体环境，提出以α-鲁棒性衡量每个智能体在遵守社会法则时能保留的保证效用比例，并给出一种通过求解一系列马尔可夫决策过程（MDP）来验证鲁棒性的方法，在若干网格玩具环境上的实验显示：当动作成功概率为1时，平行车道、对向车道以及带顺时针社会法则的交叉场景可达到α=1的鲁棒性，而强制慢速等社会法则并不总能提升保证效用。
Figure 2: Results for Different Grid Environments for Different Length and psuccess Values. The left column shows the robustness values for the simple grid environment. The middle column shows the robustness values for the grid environment with velocities. The right column shows the guaranteed utility (cost) for the grid environment with velocities, without social law, and under the social law that forces all agents to go slowly.
arXiv · 第 7 页深度剖析
提出α-鲁棒性这一度量，用于刻画随机、奖励驱动的多智能体环境中社会法则的鲁棒程度。 此前社会法则研究主要面向确定性、目标驱动设定，本文将其扩展到随机转移与奖励驱动模型，并允许智能体并发行动。 以形式化定义给出（定义4），并配套给出推论1：若环境对智能体i是α-鲁棒的且所有智能体都采用各自单智能体投影的最优策略，则智能体i至少获得α·E_i的效用。
给出一种把鲁棒性验证归约为求解一系列MDP的计算方法。 方法分两步：先最优求解各单智能体投影得到最优动作集A^{i,*}(s)，再为每个智能体构造最坏情况MDP并求解，从而得到最高可达的鲁棒水平α*。 以定理1给出α*=min_i F_i/E_i为最高可达鲁棒水平的证明，并给出算法1的步骤；同时给出在近似值函数下用上下界得到α*下界的处理方式。
说明α-鲁棒性与单智能体投影的保证效用共同给出每个智能体可保证效用的下界，从而支持设计者在不同社会法则之间做取舍。 把社会法则视为对随机博弈的变换，并用α_l·E_i^l比较不同社会法则下智能体可保证的效用。 基于推论1的推导，并以示例说明限制性强的社会法则可能鲁棒性高但保证效用低。
在网格玩具环境上的实验显示社会法则的效果依赖于场景与动作成功概率。 实验覆盖简单网格与带速度的网格，包含平行车道、对向车道、交叉角及带顺时针社会法则的交叉角等场景。 使用Python实现并采用值迭代求解MDP；在p_success=1时平行、对向及带顺时针社会法则的交叉场景达到α=1，交叉角无社会法则时鲁棒性低；在带速度网格中，强制慢速在对向车道场景于p_success=0.6和0.8时提升效用，在交叉角带顺时针社会法则时对小网格更好而对大网格更差。
启示与展望
该框架面向模型已知、奖励全为正、智能体既非对抗也非合作、需要协调以避免干扰的随机多智能体环境；社会法则被建模为对随机博弈的变换，验证需要各智能体的最优值函数或近似最优值函数。它使设计者能够在给定社会法则下计算最高可达的鲁棒水平α*，并借助α_l·E_i^l比较不同社会法则，从而为选择或评估协调机制提供依据；实验结论适用于所考察的网格玩具环境与相应参数设置。
验证依赖各智能体的最优值函数或近似最优值函数，近似情形下只能得到α*的下界；实验限于网格玩具环境，结论向更大规模或更复杂随机域的推广仍需进一步考察。后续方向包括允许智能体存在次优水平β、用强化学习求解相关MDP，以及自动合成鲁棒社会法则，其中在随机设定下搜索空间剪枝需要覆盖最坏情况MDP最优策略中出现（即使很少执行）的所有动作。若仅依据快速解析而缺少图2等图表细节，具体数值趋势的完整读取仍属开放问题。