Provably Optimal Learning Algorithms for Assistance Games¶

🕒 Published (v1): 2026-07-09 00:38 UTC · Source: Arxiv · link

Why this paper was selected

Jordan + Stuart Russell (CHAI); provably optimal algorithms for assistance/alignment games

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

TL;DR¶

This paper introduces the first provably efficient learning algorithms for online assistance games (Cooperative Inverse Reinforcement Learning), where an AI assistant must infer a human's private preferences from observed actions alone. The algorithms achieve $(1-1/e)$-approximate assistance regret at rates of $\tilde{O}(T^{3/4})$ (fully decentralized) and $\tilde{O}(T^{1/2})$ (with shared initialization), and prove this approximation factor is computationally tight.

Problem¶

Prior work on assistance games (CIRL) studied equilibria and structural properties of optimal human–AI policies but left open the algorithmic question: how can a human and an AI assistant learn near-optimal cooperative behavior efficiently when the joint policy space is exponential? No algorithm with provable efficiency or regret guarantees existed.

Method¶

The approach has two interlocking components:

Computational tractability: Joint policy optimization is reduced to online submodular maximization under matroid constraints. Each assistant policy $\pi_A: A_H \to A_A$ is encoded as an independent set in the assistance matroid $\mathcal{M}_G = (A_H \times A_A, \mathcal{I}_G)$—a partition matroid of rank $M_H$ with one slot per human action. The reward objective under best-response human play defines the value of assistance function $V_\theta(S) = \max_{(a_H,a_A)\in S} r(a_H,a_A;\theta)$, which is a weighted threshold potential with a 1-Lipschitz concave relaxation. This structure enables the RAOCO algorithm (Salem et al., 2024) to solve the centralized problem in $\text{poly}(M_H, M_A, N, T)$ time.

Decentralized coordination: A regret decomposition (Lemma 4.4) bounds assistance regret as: $$R_T^\alpha \leq R_T^{\alpha,\text{ext}}(\text{AlgC}) + R_T^{\text{track}}(\text{AlgA};\, S_T(\text{AlgC};\delta)) + \delta T$$ This separates the problem into: (i) a stable centralized human algorithm with few policy switches $S_T$, and (ii) an adaptive assistant with low tracking regret against a moving target. The human wraps the centralized algorithm; the assistant runs a tracking-regret minimizer against the human's changing recommendations.

In the pseudo-decentralized setting, the agents share a map $\varphi: A_H^* \to \Pi_A$ encoding sequences of human actions to assistant policies, enabling the tighter $\tilde{O}(\sqrt{T})$ rate.

Key Contributions¶

First computationally efficient, decentralized learning algorithms for online assistance games with provable regret guarantees.
Reduction of assistance game optimization to online submodular maximization over a partition matroid, enabling poly-time tractability despite an exponentially large joint policy space.
Regret decomposition (Lemma 4.4) identifying stability (human) and adaptivity (assistant) as the key structural properties for low assistance regret.
Proof that $(1-1/e)$ is the best achievable approximation factor for any poly-time algorithm (Theorem 4.3; hardness from reduction, tight with RP≠NP).
$\tilde{O}(\sqrt{T})$ pseudo-decentralized algorithm matching the minimax-optimal $T$-dependence up to log factors.

Results¶

Theorem 4.1: Fully decentralized algorithms achieve $(1-1/e)$-approximate assistance regret $O\!\left(M_H^{5/4}M_A^{3/4}T^{3/4}\sqrt{\log(M_AT)} + M_AM_HT\right)$, runtime $\text{poly}(M_H,M_A,N,T)$.
Theorem 4.2: Pseudo-decentralized algorithms (shared $\varphi$) achieve $(1-1/e)$-approximate assistance regret $O\!\left(M_A\sqrt{M_HT} + M_H\sqrt{M_HM_AT}\log(M_AT)\log(T)\right)$; the $\sqrt{T}$ dependence is optimal up to log factors.
Theorem 4.3: No poly-time algorithm achieves $\alpha$-approximate assistance regret sublinear in $T$ for any $\alpha > 1-1/e$, unless RP=NP.
Proposition E.6 (cited): $\Omega(\sqrt{T})$ minimax lower bound for assistance regret, confirming Theorem 4.2 is optimal.
No empirical baselines are reported; results are fully theoretical.

Limitations¶

Restricted to the oblivious adversary setting (latent preferences $\theta^{(1)},\ldots,\theta^{(T)}$ fixed before play); fundamental barriers to optimal learning under adaptive adversaries are proved in Appendix B.
The $\tilde{O}(\sqrt{T})$ algorithm requires shared initialization (a common encoding $\varphi$), which may be impractical without prior coordination.
Analysis assumes finite action and state spaces; scalability to large/continuous spaces (as in real LLM settings) is not addressed.
The $(1-1/e)$ approximation gap means the algorithms are not fully optimal, only the best achievable under poly-time constraints.
The assistant receives only bandit feedback (cannot reconstruct counterfactual rewards) and observes no direct signal of the latent state.

Relevance to Agentic AI / LLM Agents¶

This paper formalizes and solves a core challenge in AI assistance: how an agent can learn to act on behalf of a human whose private preferences are never directly communicated, only implied through actions. The assistance games / CIRL framework is a canonical theoretical model for value alignment, and these are the first algorithms with end-to-end computational and statistical guarantees, directly grounding the design of assistive AI in rigorous learning theory. The regret decomposition into human stability and assistant adaptivity maps onto a natural architectural principle for agentic systems—a planner that commits coherently and an executor that tracks plan changes efficiently. The hardness result ($\alpha > 1-1/e$ is intractable) establishes a fundamental limit on how well any efficient AI assistant can adapt to an unknown human policy, relevant to anyone designing or evaluating LLM-based assistant systems.