arXiv preprint ·
Learning vs. Optimizing Players in Budgeted Games
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Computer Science & Game Theory
Get the few papers worth your time in Computer Science & Game Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.