零和博弈的近似 Nash 均衡：Multiplicative Weights 与 Dynamic Gibbs Sampling

给 \(m\times n\) payoff matrix \(A\)，零和博弈的 equilibrium 是一个 convex--concave saddle point。经典 multiplicative weights 每轮维护两组 exponential weights；若显式归一化/采样，成本随 \(m+n\) 线性。量子算法为缓慢变化的 Gibbs 分布设计动态采样数据结构，把维数依赖降到平方根，同时输出可直接使用的稀疏经典混合策略。

1. Minimax 与 saddle gap

Row player 选

\[ p\in\Delta_m, \]

最大化 payoff；column player 选

\[ q\in\Delta_n \]

最小化。Von Neumann minimax：

\[ v=\max_{p\in\Delta_m}\min_{q\in\Delta_n}p^TAq =\min_q\max_pp^TAq. \]

定义 saddle gap

\[ \operatorname{Gap}(p,q) =\max_i(Aq)_i-min_j(p^TA)_j. \]

若 gap \(\le\epsilon\)，\((p,q)\) 是 \(\epsilon\)-approximate Nash equilibrium；任何单边 best response 最多改善 \(\epsilon\)。

2. Multiplicative weights dynamics

假设 \(A_{ij}\in[-1,1]\)。初始权重全 1。第 \(t\) 轮按

\[ p_t(i)= \frac{\exp(\eta\sum_{\tau<t}A_{i,j_\tau})} {\sum_{i'}\exp(\eta\sum_{\tau<t}A_{i',j_\tau})}, \]
\[ q_t(j)= \frac{\exp(-\eta\sum_{\tau<t}A_{i_\tau,j})} {\sum_{j'}\exp(-\eta\sum_{\tau<t}A_{i_\tau,j'})}. \]

采样 \(i_t\sim p_t,j_t\sim q_t\)，查询 \(A_{i_t,j}\) / \(A_{i,j_t}\) 对相应 loss vectors 更新。Regret bound：

\[ \frac1T\sum_t e_{i_t}^TAq \ge\max_i e_i^TA\bar q -O\!\left(\eta+\frac{\log m}{\eta T}\right) \]

及 column 对称式。取

\[ \eta=\Theta(\epsilon), \qquad T=\widetilde O(1/\epsilon^2) \]

得到 empirical strategies

\[ \bar p=\frac1T\sum_te_{i_t},\qquad \bar q=\frac1T\sum_te_{j_t} \]

的 saddle gap \(O(\epsilon)\)。

3. Classical 维数瓶颈

每轮 energy vector

\[ u_t(i)=\eta\sum_{\tau<t}A_{i,j_\tau} \]

只增加一列贡献，但若重新计算 partition function

\[ Z_t=\sum_i e^{u_t(i)} \]

并采样，需 \(O(m)\)；另一方 \(O(n)\)。数据结构/随机化后的经典总时间约

\[ \widetilde O((m+n)/\epsilon^2) \]

在相应 oracle 模型下。

4. Quantum dynamic Gibbs sampler

目标 state

\[ |p_t\rangle =Z_t^{-1/2}\sum_i e^{u_t(i)/2}|i\rangle. \]

若从均匀叠加计算 \(u_t(i)\) 并受控旋转，直接 postselection 成本取决于最大权重/normalization。动态算法利用相邻 \(u_t,u_{t+1}\) 只差一个 bounded payoff vector：

  1. 保留分层估计的权重范围与重元素；

  2. 复用上一轮 sampler/reference state；

  3. 用 rejection sampling/amplitude amplification 修正权重比 $\( e^{(u_{t+1}(i)-u_t(i))/2}; \)$

  4. 低方差 amplitude/mean estimation 更新 normalization，而不每轮从零开始。

这把一次从 \(m\) weights 采样的维数成本降到约 \(\sqrt m\)（另一方 \(\sqrt n\)），并控制 \(T\) 轮累计误差与 state disturbance。

5. 总复杂度与输出

改进算法运行时间

\[ \widetilde O\!\left( \sqrt{m+n}\,\epsilon^{-5/2} +\epsilon^{-3} \right). \]

相对早期 quantum \(\widetilde O(\sqrt{m+n}\epsilon^{-3})\) 改善精度。与 classical 维数线性式比较，在

\[ \epsilon=\Omega((m+n)^{-1}) \]

等广泛区域有 polynomial speedup；非常高精度时额外 \(\epsilon\) 幂可能主导。

输出不是 amplitude-encoded hidden strategy，而是 sample history 给出的 classical sparse distributions：最多 \(T\) 个非零支持及频数。长度

\[ O(T\log(m+n)) \]

，可直接采样/计算 payoff；避免对 \(m+n\) 维 quantum state tomography。

6. 验证与 payoff oracle

Oracle

\[ O_A|i,j,z\rangle =|i,j,z\oplus A_{ij}\rangle \]

需给足够 fixed-point 精度。验证 saddle gap 要估计

\[ \max_i(A\bar q)_i,\qquad \min_j(\bar p^TA)_j, \]

可用 quantum min/max finding + sparse support sum；失败率需在 \(T\) 轮 union bound 下放大。

算法只针对 two-player zero-sum/bilinear game。一般和 Nash equilibrium 是 PPAD 型 fixed point 问题，不能由 minimax/MWU 结果直接解决。

7. 小例子：Matching Pennies

\[\begin{split} A=\begin{pmatrix}1&-1\\-1&1\end{pmatrix}. \end{split}\]

均衡

\[ p=q=(1/2,1/2),\qquad v=0. \]

若 \(q=(1/2+\delta,1/2-\delta)\)，row best payoff \(2|\delta|\)；若 \(p\) 均匀，column 最小 payoff 0，所以 gap \(2|\delta|\)。这直接给 strategy estimation error 与 \(\epsilon\) 的关系。

8. 小结与习题

  • 零和 equilibrium 等价 convex--concave minimax saddle point。

  • MWU 的 empirical action distributions 在 \(O(1/\epsilon^2)\) 轮达到小 regret/gap。

  • Quantum dynamic Gibbs sampling 利用相邻权重缓慢变化，把 \(m+n\) 降到平方根维数依赖。

  • 稀疏经典输出避免 tomography；结果不推广到一般和 Nash。

  1. 由两方 regret bounds 推导 saddle gap。

  2. 对 Matching Pennies 计算任意 \(p,q\) 的 gap。

  3. 比较维数项与 \(\epsilon\) 项，求 quantum/classical crossover。

  4. 解释为何 empirical distribution 支持至多 \(T\)。

参考文献