Provably Optimal Learning Algorithms for Assistance Games

Nivasini Ananthakrishnan, Mark Bedaywi, Michael I. Jordan, Stuart Russell and Nika Haghtalab study how a human and assistant can learn to coordinate when they share a payoff but have different information. This entry reviews the July 9, 2026 arXiv v1 preprint. Its results concern learning algorithms in a finite mathematical game, without a human-participant study or deployed assistant evaluation.^[1]

Coordination without an agreed signal

In each round, the modeled human observes a private preference state and chooses an action. The assistant sees that action, chooses its response and receives the same reward as the human. Actions can both earn reward and communicate information; an immediately useful action need not be the most informative one (§§1,3).^[1]

The model has finite preference and action sets and rewards between zero and one. The human receives full-information feedback, allowing evaluation of counterfactual choices; the assistant receives only the reward for the action pair actually played. Preferences can vary across rounds, but their entire sequence must be fixed before play. They cannot be chosen in response to earlier interaction (§3).^[1]

What the regret guarantee measures

Assistance regret compares the reward actually earned over T rounds with the reward of the best fixed pair of policies chosen in hindsight. One policy maps preferences to human actions; the other maps those actions to assistant responses. This benchmark values how well the pair communicates and acts together, rather than only how well the assistant follows a fixed demonstrator (Definition 3.1).^[1]

The efficient algorithms use a reduced benchmark: (1 − 1/e), approximately 63%, of that best pair’s reward. Their expected sublinear regret means the expected average shortfall from this reduced benchmark approaches zero as interaction grows. It does not mean the approximation gap disappears or that every individual action is safe.^[1]

Result	Learning shortfall, suppressing logarithmic factors	Additional condition
Decentralized learning (Theorem 4.1)	T raised to the 3/4 power	A stable human-side algorithm and an assistant with suitable tracking-regret guarantees
Initially coordinated learning (Theorem 4.2)	Square root of T	A shared policy encoding and a shared random signaling string

The coordinated construction uses the shared random string to mark policy changes, then sends the new assistant policy through a sequence of human actions (Appendix D.9). This communication occupies rounds that also count toward reward.

Both bounds also depend on game dimensions; runtime is polynomial in the modeled sizes. The square-root dependence on T is optimal up to logarithmic factors for this approximation benchmark. Theorem 4.3 gives a computational barrier to improving the approximation factor while retaining efficient learning, under the assumption that RP differs from NP.^[1]

Why stability helps communication

The authors reduce joint policy optimization to a structured submodular maximization problem. They then combine a human-side learning algorithm that changes its intended policy relatively infrequently with an assistant algorithm that can track a changing target. Lemma 4.4 separates the centralized learning shortfall from the cost of coordinating the two agents (§§4–6).^[1]

Here “stable” means few policy switches. It does not establish Corrigibility or willingness to accept an intervention. The human is also an algorithmic participant with substantial information and computation, rather than an arbitrary person whose behavior the theorem fits automatically.^[1]

Historical context

Cooperative Inverse Reinforcement Learning makes teaching and learning part of a common-reward decision problem.^[2] This paper contributes efficient online learning guarantees for its repeated-game variant. Corrigible Assistance in One Round: Pragmatic-Pedagogic Best Response addresses a different restriction: goals can be signaled without sacrificing task value in an action-separable game. Its exact one-round result and this paper’s approximate repeated-learning bounds answer different computational questions.^[1][3]

Where the result stops

Appendix B constructs games in which preferences selected adaptively in response to play force linear regret. This is a limitation of the modeled learning problem; it does not say that every real person who changes their mind makes assistance impossible.^[1]

The common payoff, finite preference model, feedback and human learning procedure remain assumptions. Human Model Misspecification concerns whether such assumptions represent the actual interaction. Earlier work on literal and teaching models illustrates why a favorable matched-model result needs evidence about that match.^[4] This paper’s optimality claim therefore concerns computational efficiency and regret within the stated game, rather than complete practical alignment.^[1]