Learning vs. Optimizing Players in Budgeted Games

概要

We study repeated general games over $T$ rounds between a utility-maximizing optimizer and a learning agent, where budget constraints couple the players' decisions across rounds. Without budgets, low swap regret simultaneously guarantees the learner sublinear regret and caps the optimizer at its Stackelberg value. Budgets break this picture: adversarial no-regret becomes impossible, so the natural goals are non-manipulability---no adaptive optimizer earns more than $\mathtt{BSE} \cdot T + o(T)$, where $\mathtt{BSE}$ is its Budgeted Stackelberg Equilibrium value---and low stochastic regret when the optimizer plays a fixed mixed strategy. We give an efficient, budget-feasible learning algorithm that achieves both goals in every budgeted game: any adaptive optimizer, budgeted or not, earns at most $\mathtt{BSE} \cdot T + O(\sqrt{T})$ in expectation, and if the optimizer plays a fixed mixed strategy on each of a constant number of intervals, the learner has $O(\sqrt{T})$ regret on each such interval. Our learner best responds to forecasts of the optimizer's play that are calibrated in two novel senses, since under budgets the calibration that prevents manipulation no longer yields low stochastic regret. Response calibration, which conditions on the learner's own mixed response by embedding its continuous mixing weight as a step function in $L^2([-1,1])$, prevents manipulation without discretizing responses; dual-weighted Lagrangian calibration ensures low regret. Although low calibration error requires randomized forecasts---distributions over a continuous space that need not have a succinct representation or be directly computable---we construct such forecasts in polynomial time by simulating online gradient ascent.

参考リンク

• Paper ↗

リンク先のライセンス・再現性・データ条件をご確認ください。自動分類や実装の目安は保証ではありません。

実装を始めるプロンプト

参考リンクを確認したうえで、次の内容をコピーして利用できます。

# 論文・記事
Learning vs. Optimizing Players in Budgeted Games

# 概要
We study repeated general games over $T$ rounds between a utility-maximizing optimizer and a learning agent, where budget constraints couple the players' decisions across rounds. Without budgets, low…

# 原典
https://arxiv.org/abs/2611.05580

上記の手法を実装してください。実行前に依存関係とライセンスを確認してください。