New Algorithms Optimize Human-AI Collaboration in Assistance Games

Researchers have developed the first provably efficient learning algorithms for an online variant of assistance games, a framework where an informed human agent and an uninformed AI assistant repeatedly interact to maximize a shared reward. In this setup, the human observes a latent state of the world, while the assistant only sees the human's actions, necessitating effective collaboration to achieve optimal outcomes. The paper introduces the concept of "assistance regret," which measures the difference between the cumulative utility of interactions and the optimal joint policies achievable in hindsight. The proposed decentralized algorithms for both human and assistant agents achieve a (1-1/e)-approximate assistance regret rate of O(T^3/4), with computational complexity polynomial in the size of action and state spaces. These algorithms are versatile, compatible with any no-regret algorithm for the assistant. Furthermore, the study demonstrates that achieving a better regret approximation factor than (1-1/e) is computationally intractable. For a pseudo-decentralized setting where agents share a random string, these generic no-regret algorithms can be adapted to achieve an improved, optimal rate of O(T^1/2), up to logarithmic factors. This work provides foundational theoretical guarantees for human-AI collaborative learning.