Provably Optimal Learning Algorithms for Assistance Games

This paper studies repeated assistance games in which an informed human observes a latent world state while an uninformed assistant sees only the human’s actions. Both optimize a shared reward over T interactions. The authors introduce assistance regret and give decentralized, polynomial-time learning algorithms achieving a (1−1/e)-approximate regret rate of O~(T^{3/4}), while supporting any no-regret algorithm for the assistant. In a pseudo-decentralized setting using a shared random string, the rate improves to O~(T^{1/2}), optimal up to logarithmic factors. They also prove that improving the approximation factor beyond 1−1/e is computationally intractable.