Provably Optimal Learning Algorithms for Assistance Games

This paper addresses the challenge of designing provably efficient learning algorithms for assistance games, a framework where an informed human and an uninformed AI assistant must coordinate to optimize a shared reward function. Because the assistant only observes the human's actions and not their underlying latent preferences, the agents face a fundamental tension: actions must simultaneously serve as instruments for utility and as signals to communicate the human's private state.

The authors model this as an online learning problem and introduce the concept of assistance regret to measure performance. They overcome the exponential size of the joint policy space by reducing the problem to online submodular maximization under matroid constraints. By leveraging this structure, they develop a centralized meta-algorithm that is computationally tractable. To transition to a decentralized setting, they derive a regret-decomposition lemma that bounds the total assistance regret by the sum of the centralized algorithm's external regret and the assistant's tracking regret. This allows them to construct decentralized agents that coordinate effectively without requiring joint optimization.

The study presents two primary algorithmic results. First, they provide a decentralized algorithm that achieves (1-1/e)-approximate assistance regret at a rate of O(T^3/4) using polynomial time. Second, by introducing a shared random string for initial synchronization, they demonstrate that the regret rate can be improved to O(T^1/2), which is optimal up to logarithmic factors. Crucially, the authors prove that achieving an approximation factor better than (1-1/e) is computationally intractable (NP-hard), establishing their algorithms as essentially optimal for this class of problems.

This work bridges the gap between theoretical models of cooperative AI and practical algorithmic design. By providing the first provably efficient learning algorithms for assistance games, the paper offers a rigorous foundation for building AI systems that can learn to assist humans with private preferences in dynamic, partially observable environments. The results clarify the fundamental limits of coordination and provide a blueprint for balancing informativeness and utility in human-AI interaction.