# Provably Optimal Learning Algorithms for Assistance Games

arXiv: https://arxiv.org/abs/2607.08012 · HTML: https://mlsanity.com/paper/2607.08012/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 24 of its 58 references that are in the map.
- First posted on arXiv 9 Jul 2026.

## Builds on (most cited first, 24 of 24)

- [Does the Whole Exceed its Parts? The Effect of AI Explanations on Complementary Team Performance](https://mlsanity.com/paper/2006.14779/) (2020)
- [Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1606.03137/) (2016)
- [Multi-Agent Cooperation and the Emergence of (Natural) Language](https://mlsanity.com/paper/1612.07182/) (2016)
- [Emergent Multi-Agent Communication in the Deep Learning Era](https://mlsanity.com/paper/2006.02419/) (2020)
- [Emergence of Language with Multi-agent Games: Learning to Communicate with Sequences of Symbols](https://mlsanity.com/paper/1705.11192/) (2017)
- [Learning to Complement Humans](https://mlsanity.com/paper/2005.00582/) (2020)
- [Strongly Adaptive Online Learning](https://mlsanity.com/paper/1502.07073/) (2015)
- [The Off-Switch Game](https://mlsanity.com/paper/1611.08219/) (2016)
- [Ease-of-Teaching and Language Structure from Emergent Communication](https://mlsanity.com/paper/1906.02403/) (2019)
- [Who Leads and Who Follows in Strategic Classification?](https://mlsanity.com/paper/2106.12529/) (2021)
- [Human-Algorithm Collaboration: Achieving Complementarity and Avoiding Unfairness](https://mlsanity.com/paper/2202.08821/) (2022)
- [Learning to Communicate to Solve Riddles with Deep Distributed Recurrent Q-Networks](https://mlsanity.com/paper/1602.02672/) (2016)
- [Online learning over a finite action set with limited switching](https://mlsanity.com/paper/1803.01548/) (2018)
- [Is Learning in Games Good for the Learners?](https://mlsanity.com/paper/2305.19496/) (2023)
- [An Efficient, Generalized Bellman Update For Cooperative Inverse Reinforcement Learning](https://mlsanity.com/paper/1806.03820/) (2018)
- [Collaborative Prediction: Tractable Information Aggregation via Agreement](https://mlsanity.com/paper/2504.06075/) (2025)
- [Lazy OCO: Online Convex Optimization on a Switching Budget](https://mlsanity.com/paper/2102.03803/) (2021)
- [Human Expertise in Algorithmic Prediction](https://mlsanity.com/paper/2402.00793/) (2024)
- [On Team Decision Problems with Nonclassical Information Structures](https://mlsanity.com/paper/2101.10992/) (2021)
- [AssistanceZero: Scalably Solving Assistance Games](https://mlsanity.com/paper/2504.07091/) (2025)
- [Decentralized stochastic control](https://mlsanity.com/paper/1310.4545/) (2013)
- [Online Submodular Maximization via Online Convex Optimization](https://mlsanity.com/paper/2309.04339/) (2023)
- [Designing Algorithmic Delegates: The Role of Indistinguishability in Human-AI Handoff](https://mlsanity.com/paper/2506.03102/) (2025)
- [Regularized Conventions: Equilibrium Computation as a Model of Pragmatic Reasoning](https://mlsanity.com/paper/2311.09712/) (2023)

## Abstract (arXiv)

This paper studies an online variant of the assistance games framework, where an informed agent and an uninformed agent repeatedly interact over T timesteps to optimize a common reward function. While the informed agent (the human) observes a latent state of the world, the uninformed agent (the assistant) observes only the human's actions. We provide the first provably efficient learning algorithms for repeated assistance games. We introduce the notion of assistance regret: the gap between the cumulative utility of interactions and that of the optimal joint policies in hindsight, which map latent states to action pairs. We present decentralized algorithms for both the human and the assistant that achieve a (1-1/e)-approximate assistance regret rate of widetildeO(T3/4), with runtime polynomial in the size of the action and state spaces. These algorithms are general; in particular, they accommodate any no-regret algorithm for the assistant. We prove that achieving a regret approximation factor better than (1-1/e) is computationally intractable. Furthermore, we demonstrate how these generic no-regret algorithms can be tailored to a pseudo-decentralized setting -- using a shared random string -- to achieve a rate of widetildeO(T1/2), optimal up to logarithmic factors.