⚡ electrical engineering

An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games

本文针对具有未知动力学的两人零和线性二次博弈，提出了一种结合正则化最小二乘估计、高概率置信集及代理模型选择的在线学习方法，通过收缩步骤筛选稳定鞍点解并建立了算法的遗憾分析。

原作者： Shanting Wang, Weihao Sun, Andreas A. Malikopoulos

发布于 2026-04-06

📖 1 分钟阅读☕ 轻松阅读

原作者： Shanting Wang, Weihao Sun, Andreas A. Malikopoulos

原始论文根据 CC0 1.0（http://creativecommons.org/publicdomain/zero/1.0/）发布到公有领域。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这篇论文讲述了一个关于**“如何在完全不知道游戏规则的情况下，让两个对手学会完美博弈”**的故事。

想象一下，你正在玩一个复杂的双人电子游戏（比如赛车或策略战棋），但有一个巨大的挑战：你完全不知道游戏的物理引擎是怎么工作的（比如车子怎么加速、摩擦力是多少、对手会怎么反应）。而且，这是一个零和游戏：你赢一分，对手就输一分；反之亦然。

这篇论文就是为了解决这个问题，提出了一套**“在线学习”**（一边玩一边学）的聪明办法。

🎮 核心故事：两个对手与未知的地图

1. 场景设定：迷雾中的博弈
想象两个玩家（玩家 A 和玩家 B）在一个大迷宫里。

玩家 A 想尽可能快地到达终点（成本最小化）。
玩家 B 想尽可能拖慢 A，或者把 A 困住（成本最大化）。
问题：他们手里没有地图（不知道系统的动力学方程 $A, B_1, B_2$ 是什么），只能靠每一步的尝试来摸索。

2. 传统的笨办法 vs. 这篇论文的新招

笨办法：直接根据刚才看到的几步数据，猜一个规则，然后立刻按这个规则去控制。
- 风险：如果猜错了，可能会导致车子失控、系统崩溃，或者陷入死循环。
这篇论文的新招（认证在线学习）：
它设计了一个**“三步走”的安全策略，就像是一个谨慎的教练**在指导两个新手。

🛠️ 核心策略：教练的“三步走”教学法

第一步：收集线索（参数估计）

教练让两个玩家先试着跑几圈，记录下“我踩了油门，车走了多远”、“对手推了我一下，我偏了多少”。

利用这些数据，教练用数学方法（正则化最小二乘法）画出一张**“猜测地图”**。
但这张地图是不确定的，教练心里清楚：“这张图大概长这样，但可能有误差。”于是，他画了一个**“置信圈”**（Confidence Set），表示真正的地图大概率在这个圈里。

第二步：安全筛选（认证代理模型选择）—— 这是最精彩的部分！

这是论文最大的创新点。

问题：刚才画的那个“猜测地图”虽然大概率是对的，但万一它有点小偏差，直接用来控制可能会导致系统不稳定（比如车子直接飞出去）。
解决方案：教练不直接用“猜测地图”，而是玩一个**“缩水游戏”**。
- 他在“猜测地图”和“上一轮确定的安全地图”之间，找一条安全路线。
- 他像挤牙膏一样，把新地图往旧的安全地图里**“收缩”（Shrinkage），直到找到一个新的“代理模型”**。
- 关键点：这个新模型必须通过一个严格的**“体检”（检查广义代数 Riccati 方程是否有解），确保无论怎么控制，系统都是稳定**的，不会崩溃。
- 比喻：就像你学开车，虽然你猜出了刹车距离，但为了安全，你故意把刹车距离多算一点，确保万无一失。

第三步：微调与迭代（策略更新）

一旦找到了这个“安全且经过体检”的代理模型，教练就计算出新的最佳策略（比如：看到红灯提前多少米刹车）。
两个玩家开始执行新策略。
什么时候更新？ 只有当收集到的新数据足够多，让地图变得非常清晰时（通过“倍增技巧”判断），教练才会再次更新策略。这避免了因为一点点小数据波动就频繁改主意。

📈 结果如何？（后悔值分析）

论文不仅提出了方法，还证明了它有多好。

什么是“后悔值”（Regret）？
想象你玩了一万局游戏。如果你一开始就拥有完美地图，你的得分是 $X$ $X$ 。但你是在摸索中玩的，你的得分是 $Y$ $Y$ 。后悔值 = $Y - X$ 。
- 如果后悔值一直线性增长，说明你越玩越笨。
- 如果后悔值增长得很慢（比如随着时间平方根增长 $\sqrt{T}$ ），说明你越玩越聪明，很快就接近了大师水平。
论文结论：他们证明了，这套方法能让“后悔值”以 $\sqrt{T}$ 的速度增长。这意味着，随着游戏时间变长，你的表现会迅速收敛到最优水平，几乎和拥有完美地图的大师一样强。

🧪 实验验证

作者在电脑里模拟了这个过程：

参数估计：随着时间推移，他们猜出的“地图参数”越来越接近真实值。
策略收敛：两个玩家的“刹车/加速策略”越来越接近理论上的完美策略。
安全机制：即使原始猜测有点离谱，那个“缩水”后的安全模型依然稳稳当当，没有让系统崩溃。
后悔值曲线：那条代表“后悔值”的线，随着时间推移，变得越来越平缓，证明了学习是有效的。

💡 总结：这篇论文在说什么？

简单来说，这篇论文发明了一套**“带安全锁的在线学习算法”**。

它解决了在完全不知道系统规则的情况下，两个互相竞争的对手如何安全、稳定且高效地学会最佳策略的问题。它通过**“先猜测，再安全收缩，最后验证”**的机制，确保了学习过程不会把系统搞崩，并且从数学上证明了这种方法最终一定能达到最优水平。

一句话比喻：
这就好比两个盲人下棋，他们看不见棋盘，只能靠摸子。这篇论文教他们：“别急着按摸到的感觉走，先画个大概的图，然后为了安全，把图往保守的方向改一改，确认不会撞墙了再走。走几步，再修正一下图。这样，你们最终能下出和明眼人一样精彩的棋局。”

这是一份关于论文《An Online Learning Approach for Two-Player Zero-Sum Linear Quadratic Games》（一种针对双玩家零和线性二次博弈的在线学习方法）的详细技术总结。

1. 问题背景 (Problem Formulation)

核心问题：研究在系统动力学未知的情况下，如何为双玩家零和线性二次（LQ）博弈设计在线学习算法。
应用场景：此类博弈广泛应用于多机器人协调、自动驾驶及安全关键控制系统，其中两个决策者（玩家）的目标完全对立（一个最小化成本，一个最大化成本）。
挑战：
- 与单智能体 LQR 不同，双玩家博弈中策略是耦合的，且存在对抗性交互。
- 系统矩阵 $(A, B_1, B_2)$ 未知，必须从观测数据中学习。
- 学习过程中必须保证系统的稳定性（Stability）。直接基于估计模型求解广义代数黎卡提方程（GARE）可能导致模型不稳定或无解（即不存在稳定鞍点解）。
目标：设计一个在线学习算法，使其累积遗憾（Regret）随时间呈次线性增长（Sublinear growth），即 $O(\sqrt{T})$ ，从而保证长期控制性能接近最优纳什均衡。

2. 方法论 (Methodology)

论文提出了一种认证在线学习框架（Certified Online Learning Framework），主要包含以下关键步骤：

A. 参数估计与置信集构建

岭回归估计：利用观测到的状态和输入数据，通过岭回归（Ridge Regression）估计系统参数矩阵 $\Theta = [A, B_1, B_2]$ 。
高概率置信集：基于自归一化鞅浓度不等式（Self-normalized martingale concentration），构建参数估计值 $\hat{\theta}_k$ 的高概率置信椭球 $C_k(\delta)$ 。这确保了真实参数以高概率落在该集合内。

B. 认证代理模型选择 (Certified Surrogate Model Selection)

这是本文的核心创新点，旨在解决“估计模型可能不稳定”的问题：

正则性要求：定义了一个正则参数集合 $\theta_{reg}(\mu, \gamma)$ $θ_{r e g} (μ, γ)$ ，要求在该集合内的模型满足：
1. GARE 存在半正定稳定解 $P(\theta)$ 。
2. 可解性边界满足 $R_v - B_2^\top P(\theta) B_2 \succeq \mu I$ 。
3. 闭环系统矩阵是 Schur 稳定的（谱半径 $\le 1-\gamma$ ）。
收缩步骤 (Shrinkage Step)：
- 不直接使用估计值 $\hat{\theta}_k$ 求解策略。
- 在置信集 $C_k(\delta)$ 内，沿着当前认证模型 $\tilde{\theta}_{k-1}$ 和最新估计值 $\hat{\theta}_k$ 的连线进行收缩搜索。
- 寻找最大的步长 $\alpha_k \in [0, 1]$ ，使得组合模型 $\tilde{\theta}_k = (1-\alpha_k)\tilde{\theta}_{k-1} + \alpha_k \hat{\theta}_k$ 同时满足置信集约束和正则性约束（即 $\tilde{\theta}_k \in C_k(\delta) \cap \theta_{reg}$ ）。
- 这确保了用于计算策略的代理模型始终是“安全”且稳定的。

C. 策略更新与探索

策略计算：基于选定的认证代理模型 $\tilde{\theta}_k$ 求解 GARE，得到纳什均衡增益 $(K_k, L_k)$ 。
更新机制：采用“倍增技巧”（Doubling Trick），仅当信息矩阵的行列式增长到一定程度时才更新策略，以减少不必要的重计算。
探索信号：在控制输入中加入有界的高斯噪声（ $\eta_t, \zeta_t$ ），以满足持续激励（Persistent Excitation）条件，确保参数估计的收敛性。

3. 主要贡献 (Key Contributions)

首个认证算法：提出了首个针对未知动力学双玩家零和 LQ 博弈的认证在线学习算法。该算法不仅学习策略，还通过数学证明保证了学习过程中的稳定性。
次线性遗憾界：建立了算法的累积遗憾上界为 $O(\sqrt{T})$ 。这是通过分解遗憾为瞬态项、探索项和策略间隙项，并利用参数估计误差与黎卡提解的 Lipschitz 连续性推导得出的。
理论分析：
- 证明了在正则区域内，GARE 的解（黎卡提矩阵 $P$ 和增益 $K, L$ ）关于系统参数是连续可微的。
- 证明了小模型误差会导致成比例的小策略误差，从而保证了性能损失的有界性。
数值验证：通过仿真实验验证了模型估计误差、反馈增益误差随时间收敛，且归一化遗憾保持有界，符合理论预测。

4. 实验结果 (Results)

参数估计：随着数据积累，认证代理模型 $\tilde{\theta}_k$ 的估计误差 $\|\tilde{\theta}_k - \theta^*\|$ 逐渐减小并收敛于真实值。
策略收敛：计算出的反馈增益 $(K_k, L_k)$ 逐渐逼近真实的纳什均衡增益 $(K^*, L^*)$ 。
代理模型的作用：实验显示，原始估计值 $\hat{\theta}_k$ 的误差有时较大，而经过收缩步骤后的认证模型 $\tilde{\theta}_k$ 误差更小且更保守，确保了 GARE 的可解性。
遗憾表现：累积遗憾随时间增长，但归一化后的遗憾（除以 $\sqrt{T}$ ）保持有界并趋于稳定，验证了 $O(\sqrt{T})$ 的遗憾界。

5. 意义与展望 (Significance & Future Work)

理论意义：填补了在线学习在对抗性多智能体博弈（特别是零和博弈）中缺乏严格稳定性保证的空白。解决了“学习”与“稳定性”之间的权衡难题。
实际应用：为安全关键系统（如自动驾驶对抗、网络安全防御）提供了一种在未知环境下安全学习最优策略的可行方案。
未来方向：
- 放宽对“持续激励”假设的依赖。
- 将算法扩展至部分可观测博弈、多玩家博弈以及时变系统。

总结：该论文通过引入“认证代理模型选择”和“收缩机制”，成功地在未知动力学的对抗性博弈中实现了稳定且高效的在线学习，并给出了严格的遗憾理论保证，是控制理论与机器学习交叉领域的重要进展。