Provably Optimal Learning Algorithms for Assistance Games

# Provably Optimal Learning Algorithms for Assistance Games
Source: [https://arxiv.org/html/2607.08012](https://arxiv.org/html/2607.08012)
Mark BedaywiMichael I\. JordanStuart RussellNika Haghtalab

###### Abstract

This paper studies an online variant of the*assistance games*framework, where an informed agent and an uninformed agent repeatedly interact overTTtimesteps to optimize a common reward function\. While the informed agent \(the human\) observes a latent state of the world, the uninformed agent \(the assistant\) observes only the human’s actions\. We provide the first provably efficient learning algorithms for repeated assistance games\. We introduce the notion of*assistance regret*: the gap between the cumulative utility of interactions and that of the optimal joint policies in hindsight, which map latent states to action pairs\. We present decentralized algorithms for both the human and the assistant that achieve a\(1−1/e\)\(1\-1/e\)\-approximate assistance regret rate of𝒪~​\(T3/4\)\\tilde\{\\mathcal\{O\}\}\\left\(T^\{3/4\}\\right\), with runtime polynomial in the size of the action and state spaces\. These algorithms are general; in particular, they accommodate any no\-regret algorithm for the assistant\. We prove that achieving a regret approximation factor better than\(1−1/e\)\(1\-1/e\)is computationally intractable\. Furthermore, we demonstrate how these generic no\-regret algorithms can be tailored to a pseudo\-decentralized setting—using a shared random string—to achieve a rate of𝒪~​\(T1/2\)\\tilde\{\\mathcal\{O\}\}\\left\(T^\{1/2\}\\right\), optimal up to logarithmic factors\.

## 1Introduction

Consider a repeated interaction between two cooperative agents who share a common objective but have asymmetric access to information\. One agent observes a changing latent state—such as a preference, type, or objective—while the other must act based only on indirect signals produced by the first agent\. Such settings arise naturally in abstractions of human–assistant interaction, cooperative multi\-agent systems, training of assistive AI, and emergent communication, where the former agent represents a human principal with private preferences and the latter represents an AI assistant seeking to act on the human’s behalf\.

Despite the absence of strategic misalignment in utilities, coordination in these environments poses a fundamental challenge\. On the one hand, the lack of a shared frame of reference or common language means that the agents must learn how to communicate by observing each other’s actions over time\. On the other hand, actions simultaneously generate utility, causing them to serve a dual role as instruments for achieving reward and signals for conveying the latent state\. This tension between informativeness and utility lies at the core of the problem\.

One theoretical perspective for capturing these challenges is the*assistance games*framework, also known as*Cooperative Inverse Reinforcement Learning*\(Hadfield\-Menell et al\.,[2016](https://arxiv.org/html/2607.08012#bib.bib24)\)\. This framework models interactions between a human and an assistive AI system as a cooperative game with partial observability\. Prior work has studied equilibria and structural properties of optimal assistive policies—for example, tradeoffs between the informativeness and utility of actions—but the algorithmic problem of computing and learning such policies has been unexplored\.

In this paper, we introduce anonline variant of assistance games and give computationally efficient, decentralized algorithms for learning near\-optimal policies for both the human and the assistant\.

Our model captures repeated interaction between an informed agent \(the human\) and an uninformed agent \(the assistant\)\. In each roundtt, a latent stateθ\(t\)∈Θ\\theta^\{\(t\)\}\\in\\Theta—possibly drawn from a nonstationary process—is realized and observed only by the human\. This state represents private information about the human’s preferences or objectives\. The human selects an actionaH\(t\)a\_\{H\}^\{\(t\)\}from a finite action space𝒜H\\mathcal\{A\}\_\{H\}of sizeMHM\_\{H\}\. The assistant observesaH\(t\)a\_\{H\}^\{\(t\)\}, but notθ\(t\)\\theta^\{\(t\)\}, and responds with an actionaA\(t\)a\_\{A\}^\{\(t\)\}from a finite action space𝒜A\\mathcal\{A\}\_\{A\}of sizeMAM\_\{A\}\. Both agents then receive a common rewardr​\(aH\(t\),aA\(t\);θ\(t\)\),r\\\!\\left\(a\_\{H\}^\{\(t\)\},a\_\{A\}^\{\(t\)\};\\theta^\{\(t\)\}\\right\),which depends on the joint actions and the human’s private state\.

To measure performance, we consider the space of*joint*human–assistant policies: pairs\(πH,πA\)\(\\pi\_\{H\},\\pi\_\{A\}\)where a human policyπH:Θ→𝒜H\\pi\_\{H\}:\\Theta\\to\\mathcal\{A\}\_\{H\}maps latent states to human actions and an assistant policyπA:𝒜H→𝒜A\\pi\_\{A\}:\\mathcal\{A\}\_\{H\}\\to\\mathcal\{A\}\_\{A\}maps human actions to assistant actions\. We measure success via*α\\alpha\-approximate assistance regret*\([Definition˜3\.1](https://arxiv.org/html/2607.08012#S3.Thmtheorem1)\): the gap between the agents’ cumulative reward and anα\\alphafactor of the cumulative reward of the best joint policy in hindsight\.

Our main result gives a pair of decentralized learning algorithms for the human and the assistant that achieve\(1−1/e\)\(1\-1/e\)\-approximate assistance regret at a rate of𝒪~​\(T3/4\)\\tilde\{\\mathcal\{O\}\}\\left\(T^\{3/4\}\\right\)in timepoly​\(N,MH,MA\)\\mathrm\{poly\}\(N,M\_\{H\},M\_\{A\}\)\([Theorem˜4\.1](https://arxiv.org/html/2607.08012#S4.Thmtheorem1)\); with light initial coordination—a shared encoding from human action sequences to assistant policies—this rate improves to𝒪~​\(T\)\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{T\}\\right\), optimal inTTup to logarithmic factors \([Theorem˜4\.2](https://arxiv.org/html/2607.08012#S4.Thmtheorem2)\)\. Two technical ingredients drive the result\. First is a reduction casting joint policy optimization in assistance games as online submodular maximization with matroid constraints \([Lemmas˜D\.1](https://arxiv.org/html/2607.08012#A4.Thmtheorem1)and[5\.4](https://arxiv.org/html/2607.08012#S5.Thmtheorem4)\)\. This reduction enables computational tractability despite exponential size of the joint policy space by leveraging the structure of submodular functions\. Second is a regret\-decomposition lemma \([Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)\) that bounds assistance regret by the centralized algorithm’s external regret, its number of policy switches, and the assistant’s tracking regret against a moving target\. This decomposition guides our design toward two structural properties:*stability*\(few policy switches\) for the human and*adaptivity*\(low tracking regret\) for the assistant\. The approximation factor of1−1/e1\-1/eis tight: no efficient algorithm achieves sublinearα\\alpha\-approximate assistance regret forα\>1−1/e\\alpha\>1\-1/eunless𝖱𝖯=𝖭𝖯\\mathsf\{RP\}=\\mathsf\{NP\}\([Theorem˜4\.3](https://arxiv.org/html/2607.08012#S4.Thmtheorem3)\)\.

## 2Related Work

The idea of modeling the problem of AI assistance mathematically had been first proposed almost ten years ago in work includingFern et al\. \([2014](https://arxiv.org/html/2607.08012#bib.bib17)\)andHadfield\-Menell et al\. \([2016](https://arxiv.org/html/2607.08012#bib.bib24)\)\.Shah et al\. \([2020](https://arxiv.org/html/2607.08012#bib.bib52)\)show that such an assistant would be able to better satisfy human preferences than traditional reward learning algorithms, andHadfield\-Menell et al\. \([2016](https://arxiv.org/html/2607.08012#bib.bib24),[2017](https://arxiv.org/html/2607.08012#bib.bib25)\)show that an optimal assistant would avoid issues of misalignment to human values\.Malik et al\. \([2018](https://arxiv.org/html/2607.08012#bib.bib44)\)andLaidlaw et al\. \([2025](https://arxiv.org/html/2607.08012#bib.bib37)\)propose algorithms for solving assistance games that are empirically performant, but the problem of designing learning algorithms that provably play such games optimally remains open\. Similar to us, previous work has also taken the approach of reducing the assistance games problem to other classes of problems — particularly to classes of Partially Observable Markov Decision Processes \(POMDPs\)\. We introduce a new reduction with a mathematical structure that allows us to demonstrate provable optimality guarantees\. A particular subclass of assistance games are*communication games*\. We describe related works on this literature in more detail in[Appendix˜F](https://arxiv.org/html/2607.08012#A6)\.

Our work is related to literature on equilibrium computation\. We can frame our goals is decentralized learning of optimal equilibria in assistance games\. Computing the optimal equilibrium is computationally intractable\(Gilboa and Zemel,[1989](https://arxiv.org/html/2607.08012#bib.bib21)\)in general, including in games of common interest\(Chu and Halpern,[2001](https://arxiv.org/html/2607.08012#bib.bib11); Conitzer and Sandholm,[2006](https://arxiv.org/html/2607.08012#bib.bib13)\)\. In common interest games, the optimal equilibrium is also each player’s Stackelberg equilibrium\. The computational tractability of computing the Stackelberg equilibrium is shown to depend on the geometry of the game and can be intractable in general\(Letchford et al\.,[2009](https://arxiv.org/html/2607.08012#bib.bib40); Peng et al\.,[2019](https://arxiv.org/html/2607.08012#bib.bib47)\)\. For games where the Stackelberg equilibrium can be computed efficiently, convergence to the Stackelberg equilibrium can be achieved through dynamics where one player’s learning dynamic is more stable than the other\(Brown et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib7); Zrnic et al\.,[2021](https://arxiv.org/html/2607.08012#bib.bib58)\)\. The learning dynamics we propose for communication games also satisfy this property\.

Other areas studying cooperative interactions between agents include work on team decision theory \(e\.g\.Radner \([1962](https://arxiv.org/html/2607.08012#bib.bib48)\); Ho et al\. \([1972](https://arxiv.org/html/2607.08012#bib.bib29)\); Nayyar et al\. \([2013](https://arxiv.org/html/2607.08012#bib.bib46)\); Mahajan and Mannan \([2016](https://arxiv.org/html/2607.08012#bib.bib43)\); Malikopoulos \([2022](https://arxiv.org/html/2607.08012#bib.bib45)\)\) which takes a control theoretic approach to studying optimal cooperation, and work on human\-AI collaboration studying when human\-AI systems achieve complementarity i\.e\., better performance than the sum of individual components \(e\.g\.,Green and Chen \([2019](https://arxiv.org/html/2607.08012#bib.bib22)\); Bansal et al\. \([2021](https://arxiv.org/html/2607.08012#bib.bib6)\); Wilder et al\. \([2020](https://arxiv.org/html/2607.08012#bib.bib57)\); Steyvers et al\. \([2022](https://arxiv.org/html/2607.08012#bib.bib55)\); Donahue et al\. \([2022](https://arxiv.org/html/2607.08012#bib.bib15)\); Athey et al\. \([2020](https://arxiv.org/html/2607.08012#bib.bib5)\); Alur et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib3)\); Greenwood et al\. \([2025](https://arxiv.org/html/2607.08012#bib.bib23)\); Collina et al\. \([2026](https://arxiv.org/html/2607.08012#bib.bib12)\)\)

## 3Model and Preliminaries

The online assistance game is defined by a preference spaceΘ\\Thetaof sizeNN, two sets of actions𝒜H\\mathcal\{A\}\_\{H\}and𝒜A\\mathcal\{A\}\_\{A\}of sizesMHM\_\{H\}andMAM\_\{A\}respectively, and a bounded reward functionr:𝒜H×𝒜A×Θ→\[0,1\]r:\\mathcal\{A\}\_\{H\}\\times\\mathcal\{A\}\_\{A\}\\times\\Theta\\to\[0,1\]\. Two agents, an assistant and a human, repeatedly play the game overTTrounds\. First, nature fixes preferencesθ\(1\),…,θ\(T\)∈Θ\\theta^\{\(1\)\},\\dots,\\theta^\{\(T\)\}\\in\\Thetabefore play\. Then, every roundt∈\[T\]t\\in\[T\]of the assistance game involves the following steps:

1. 1\.The human observesθ\(t\)\\theta^\{\(t\)\}and plays an actionaH\(t\)∈𝒜Ha\_\{H\}^\{\(t\)\}\\in\\mathcal\{A\}\_\{H\}\.
2. 2\.The assistant sees only the actionaH\(t\)a\_\{H\}^\{\(t\)\}the human takes, and not the preferenceθ\(t\)\\theta^\{\(t\)\}\. The assistant then takes the actionaA\(t\)∈𝒜Aa\_\{A\}^\{\(t\)\}\\in\\mathcal\{A\}\_\{A\}in response\.
3. 3\.Both the assistant and the human receive the rewardr​\(aH\(t\),aA\(t\);θ\(t\)\)r\\left\(a\_\{H\}^\{\(t\)\},a\_\{A\}^\{\(t\)\};\\theta^\{\(t\)\}\\right\)\.

The parameterθ\(t\)\\theta^\{\(t\)\}captures the human’s preference at roundtt\. We allow the preferenceθ\(t\)\\theta^\{\(t\)\}to change over time, allowing robustness to changing human preferences\. However, we impose the restriction that the sequence of preferences is fixed before the game begins\. That is, the preference at each round cannot be selected adaptively based on previous rounds of interaction\. We call this the*oblivious*setting\. The stronger model of an adversary who can select the preferenceθ\(t\)\\theta^\{\(t\)\}adversarially based on previous rounds of interaction is called the*adaptive*setting\. We prove in[Appendix˜B](https://arxiv.org/html/2607.08012#A2)that there are fundamental limitations to learning optimal assistance in the adaptive setting\.

The assistant receives bandit feedback: it observes the action pairaH\(t\),aA\(t\)a\_\{H\}^\{\(t\)\},a\_\{A\}^\{\(t\)\}and the corresponding rewardr​\(aH\(t\),aA\(t\);θ\(t\)\)r\\left\(a\_\{H\}^\{\(t\)\},a\_\{A\}^\{\(t\)\};\\theta^\{\(t\)\}\\right\), but because it does not have access toθ\(t\)\\theta^\{\(t\)\}, it cannot reconstruct counterfactual rewards\. In contrast, the human, because they also observeθ\(t\)\\theta^\{\(t\)\}, receives full\-information feedback\.

In the normal form representation of the assistance game, the human’s policy space is the setΠH\\Pi\_\{H\}of mappings from the human’s private preference to human’s actions,πH:Θ→𝒜H\\pi\_\{H\}:\\Theta\\to\\mathcal\{A\}\_\{H\}, and the assistant’s policy space is the setΠA\\Pi\_\{A\}of mappings from an observed human action to an assistant action,πA:𝒜H→𝒜A\\pi\_\{A\}:\\mathcal\{A\}\_\{H\}\\to\\mathcal\{A\}\_\{A\}\. For notational convenience, we writer​\(πH,πA;θ\)r\(\\pi\_\{H\},\\pi\_\{A\};\\theta\)to mean the reward the human and assistant receive when they play policyπH\\pi\_\{H\}andπA\\pi\_\{A\}when the human’s preferences areθ\\theta, mathematicallyr​\(πH​\(θ\),πA​\(πH​\(θ\)\);θ\)r\(\\pi\_\{H\}\(\\theta\),~\\pi\_\{A\}\(\\pi\_\{H\}\(\\theta\)\);~\\theta\)\.

We introduce a notion of \(approximate\)regret to measure the joint success of the human and assistant in the online assistance game\. We call this the*assistance regret*and simply refer to this as regret in the remainder of the paper\. Assistance regret is defined in the following definition\.

###### Definition 3\.1\(α\\alpha\-Assistance regret\)\.

For a fixedα∈\[0,1\]\\alpha\\in\[0,1\], theα\\alpha\-assistance regret of a sequenceχ=\(θ\(t\),πH\(t\),πA\(t\)\)t=1T\\chi=\\left\(\\theta^\{\(t\)\},\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\\right\)\_\{t=1\}^\{T\}, writtenRTα​\(χ\)R^\{\\alpha\}\_\{T\}\(\\chi\), is:

α​\(maxπH∗∈ΠH,πA∗∈ΠA​∑t=1Tr​\(πH∗,πA∗;θ\(t\)\)\)−∑t=1Tr​\(πH\(t\),πA\(t\);θ\(t\)\)\.\\displaystyle\\alpha\\left\(\\max\_\{\\pi\_\{H\}^\{\*\}\\in\\Pi\_\{H\},\\pi\_\{A\}^\{\*\}\\in\\Pi\_\{A\}\}\\sum\_\{t=1\}^\{T\}r\\left\(\\pi\_\{H\}^\{\*\},\\pi\_\{A\}^\{\*\};\\theta^\{\(t\)\}\\right\)\\right\)\-\\sum\_\{t=1\}^\{T\}r\\left\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\};\\theta^\{\(t\)\}\\right\)\.We suppressθ\(t\)\\theta^\{\(t\)\}in the regret notion when it is clear from context and denotert​\(πH,πA\)=r​\(πH,πA;θ\(t\)\)r\_\{t\}\(\\pi\_\{H\},\\pi\_\{A\}\)=r\(\\pi\_\{H\},\\pi\_\{A\};\\theta^\{\(t\)\}\)\. We also refer toRT​\(Alg\)R\_\{T\}\(\\mathrm\{Alg\}\)as the min\-maxα\\alpha\-assistance regret of algorithmAlg\\mathrm\{Alg\}\.

### 3\.1Submodular Maximization With Matroid Constraints

Our results will rely on tools from submodular maximization and matroid theory\. We will describe the necessary tools in this section\. Given an arbitrary set of elements𝒰\\mathcal\{U\}, a set function over𝒰\\mathcal\{U\}is a mapping from subsets in𝒰\\mathcal\{U\}to real numbers,f:2𝒰→ℝf:2^\{\\mathcal\{U\}\}\\to\\mathbb\{R\}\.

A set function is said to be monotone when adding any element can only increase the value of the function\. That isffis monotone when for allS⊆𝒰S\\subseteq\\mathcal\{U\}and allx∉Sx\\notin S, it holds thatf​\(S∪\{x\}\)≥f​\(S\)f\(S\\cup\\\{x\\\}\)\\geq f\(S\)\.

A set function is said to be submodular when the marginal improvement of adding an element can only decrease as the size of the set increases\.

###### Definition 3\.2\(Submodularity\)\.

Letffbe a set function on a set𝒰\\mathcal\{U\}\.ffis said to besubmodularwhen, for allS′⊆S⊆𝒰S^\{\\prime\}\\subseteq S\\subseteq\\mathcal\{U\}and allx∉Sx\\notin S, the increase in value after addingxxtoSSis smaller than the increase in value after addingxxtoS′S^\{\\prime\}\. That is,f​\(S∪\{x\}\)−f​\(S\)≤f​\(S′∪\{x\}\)−f​\(S′\)f\(S\\cup\\\{x\\\}\)\-f\(S\)\\leq f\(S^\{\\prime\}\\cup\\\{x\\\}\)\-f\(S^\{\\prime\}\)\.

We will consider the constrained maximization of submodular functions under matroid constraints\.

###### Definition 3\.3\(Matroids\)\.

A pairℳ=\(𝒰,ℐ\)\\mathcal\{M\}=\(\\mathcal\{U\},\\mathcal\{I\}\)is amatroidwhen𝒰\\mathcal\{U\}is a finite set, andℐ⊆2𝒰\\mathcal\{I\}\\subseteq 2^\{\\mathcal\{U\}\}is a collection of subsets of𝒰\\mathcal\{U\}such that 1\) For allI∈ℐI\\in\\mathcal\{I\}, ifJ⊆IJ\\subseteq I, thenJ∈ℐJ\\in\\mathcal\{I\}and 2\) For allI,J∈ℐI,J\\in\\mathcal\{I\}, if\|J\|<\|I\|\\left\|J\\right\|<\\left\|I\\right\|, then there exists somee∈I∖Je\\in I\\setminus Jsuch thatJ∪\{e\}∈ℐJ\\cup\\\{e\\\}\\in\\mathcal\{I\}\.

Any set inI∈ℐI\\in\\mathcal\{I\}is said to be anindependent set\. The maximum size of an independent set inℐ\\mathcal\{I\}is said to be therankof the matroidℳ\\mathcal\{M\}\.

Our results actually rely on a special subclass of submodular functions i\.e\.,*weighted threshold potentials*\(a sum of capped linear functions;[Definition˜A\.2](https://arxiv.org/html/2607.08012#A1.Thmtheorem2)\) and on a special subclass of matroids i\.e\.,*partition matroids*\([Definition˜A\.3](https://arxiv.org/html/2607.08012#A1.Thmtheorem3)\)\. We provide more details on these subclasses in[Appendix˜A](https://arxiv.org/html/2607.08012#A1)\.

### 3\.2Background on Online Learning

Regret notions and algorithms originating from the online learning literature will play a central role in our paper\.

In a setting with action set\[K\]\[K\]andTTrounds, for sequences of actions and reward functions\(at,rt\)\(a\_\{t\},r\_\{t\}\)whereat∈\[K\]a\_\{t\}\\in\[K\]andrt:\[K\]→\[0,1\]r\_\{t\}:\[K\]\\to\[0,1\], we can define the following notions of regret that we will make extensive use of in framing our results\.

###### Definition 3\.4\(External regret and number of switches\)\.

Theα\\alpha\-approximate external regret of a sequenceχ=\(at,rt\)t=1T\\chi=\(a\_\{t\},r\_\{t\}\)\_\{t=1\}^\{T\}isRTα,ext​\(χ\)=α​maxa∈\[K\]​∑t=1Trt​\(a\)−∑t=1Trt​\(at\)R\_\{T\}^\{\\alpha,\\mathrm\{ext\}\}\(\\chi\)=\\alpha\\max\_\{a\\in\[K\]\}\\sum\_\{t=1\}^\{T\}r\_\{t\}\(a\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\(a\_\{t\}\)\. The number of switches in the sequence is∑t=2T𝟏​\{at≠at−1\}\\sum\_\{t=2\}^\{T\}\\mathbf\{1\}\\\{a\_\{t\}\\neq a\_\{t\-1\}\\\}\.

###### Definition 3\.5\(Tracking regret withppsegments\)\.

Tracking regret\(Herbster and Warmuth,[1998](https://arxiv.org/html/2607.08012#bib.bib28)\)measures a learner’s ability to compete with a sequence of app\-times changing benchmark of actions rather than a single best fixed action\. For a sequenceχ=\(at,rt\)t=1T\\chi=\(a\_\{t\},r\_\{t\}\)\_\{t=1\}^\{T\}, the tracking regret is defined as :

RTtrack​\(χ;p\)=maxs1<⋯<sp\+1∈\[T\+1\]s1=1,sp\+1=T\+1b1,…,bp∈\[K\]​∑i=1p∑t=sisi\+1−1rt​\(bi\)−∑t=1Trt​\(at\)\.R\_\{T\}^\{\\text\{track\}\}\(\\chi;p\)=\\max\_\{\\begin\{subarray\}\{c\}s\_\{1\}<\\dots<s\_\{p\+1\}\\in\[T\+1\]\\\\ s\_\{1\}=1,s\_\{p\+1\}=T\+1\\\\ b\_\{1\},\\dots,b\_\{p\}\\in\[K\]\\end\{subarray\}\}\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}r\_\{t\}\(b\_\{i\}\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\(a\_\{t\}\)\.This regret formulation is useful in changing environments where the optimal action varies over time\.

*Feedback models\.*Online learning algorithms select actionata\_\{t\}in a roundttbased on the available history consisting of actions and feedback of previous rounds\. In a*full\-information*setting the entire reward functionrtr\_\{t\}is revealed as feedback at the end of roundtt\. In abanditsetting, only the reward of the selected actionrt​\(at\)r\_\{t\}\(a\_\{t\}\)is revealed as feedback\.

## 4Main Results and Techniques

Our main results provide pairs of decentralized learning algorithms for the human and the assistant that are computationally efficient and result in sublinear\(1−1/e\)\(1\-1/e\)\-approximate assistance regret\. We first state our main theorems, discuss the optimality of the guarantees stated in these theorems, and finally describe the main ideas behind constructing these algorithms\.

Our first theorem constructs decentralized algorithms that use quite general regret minimization algorithms and achieve a𝒪~​\(T3/4\)\\tilde\{\\mathcal\{O\}\}\\left\(T^\{3/4\}\\right\)rate of\(1−1/e\)\(1\-1/e\)\-approximate assistance regret\.

###### Theorem 4\.1\.

There arepoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time learning algorithms for the human and assistant that achieve no\-\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-approximate regret at a rate of𝒪​\(MH5/4​MA3/4​T3/4​log⁡\(MA​T\)\+MA​MH​T\)\\mathcal\{O\}\\left\(M\_\{H\}^\{5/4\}M\_\{A\}^\{3/4\}T^\{3/4\}\\log\(M\_\{A\}T\)\+M\_\{A\}M\_\{H\}\\sqrt\{T\}\\right\)\.

Moreover, any assistant algorithm with minmax optimal tracking regret rates can be used to obtain this bound\.

Our second theorem constructs decentralized algorithms that are more tailored to the assistance game and achieve a tighter𝒪~​\(T\)\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{T\}\\right\)rate of\(1−1/e\)\(1\-1/e\)\-approximate assistance regret\. These algorithms require some initial synchronization between the human and assistant in the form of holding a shared mapping from sequences of human actions to the policy space\.

###### Theorem 4\.2\.

There arepoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time learning algorithms for the human and assistant that make use of a shared mapϕ:𝒜H∗→ΠA\\phi:\\mathcal\{A\}\_\{H\}^\{\*\}\\rightarrow\\Pi\_\{A\}from sequences of human actions to assistant policies and achieve no\-\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-approximate regret at a rate of𝒪​\(MA​MH​T\+MH​MH​MA​T​log⁡\(MA​T\)​log⁡\(T\)\)\\mathcal\{O\}\\left\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\+M\_\{H\}\\sqrt\{M\_\{H\}M\_\{A\}T\}\\,\\log\(M\_\{A\}T\)\\log\(T\)\\right\)\.

We will describe the main ideas behind constructing these algorithms in this section, deferring the full proofs to[Sections˜D\.8](https://arxiv.org/html/2607.08012#A4.SS8)and[D\.9](https://arxiv.org/html/2607.08012#A4.SS9)\. But first, let us discuss the optimality of the regret guarantees\. Note that guarantees we achieve in both settings of with and without initial synchronization is for assistance regret with a level of\(1−1/e\)\(1\-1/e\)\-approximation\. It turns out that it is not tractable to achieve sublinear assistance regret with a better approximation factor, which we state in[Theorem˜4\.3](https://arxiv.org/html/2607.08012#S4.Thmtheorem3)\.

###### Theorem 4\.3\.

UnlessRP=NP\\text\{RP\}=\\text\{NP\}, for anyα\>1−1/e\\alpha\>1\-\\nicefrac\{\{1\}\}\{\{e\}\}, any algorithm that runs in timepoly​\(N,MH,MA\)\\text\{poly\}\(N,M\_\{H\},M\_\{A\}\)per iteration hasα\\alpha\-approximate assistance regret such that eitherRTα∈ω​\(T1−ϵ\)R^\{\\alpha\}\_\{T\}\\in\\omega\(T^\{1\-\\epsilon\}\)for allϵ\>0\\epsilon\>0orRTα∉poly​\(N,MH,MA\)R^\{\\alpha\}\_\{T\}\\notin\\text\{poly\}\(N,M\_\{H\},M\_\{A\}\)\.

We prove this in[Appendix˜C](https://arxiv.org/html/2607.08012#A3)\. Given this approximation factor, the regret bound in[Theorem˜4\.2](https://arxiv.org/html/2607.08012#S4.Thmtheorem2)has aT\\sqrt\{T\}dependence on the number of roundsTTup to logarithmic factors, which is optimal due to standard minmax lower bounds for regret minimization\. This is formalized for assistance games in[Proposition˜E\.6](https://arxiv.org/html/2607.08012#A5.Thmtheorem6)\.

### 4\.1Central Challenges and Techniques

There are two central challenges that the human\-assistant system needs to overcome to have low assistance regret\. The first is*computational*: the space of human\-assistant policy pairs is exponential in size\. The second is a*coordination*challenge: the human and assistant need to learn jointly optimal strategies despite learning being decentralized\. We address these challenges in more detail in[Section˜5](https://arxiv.org/html/2607.08012#S5)and[Section˜6](https://arxiv.org/html/2607.08012#S6)respectively\.

#### Challenge 1: Computational tractability of joint optimization \([Section˜5](https://arxiv.org/html/2607.08012#S5)\)\.

The space of all joint human\-assistant policy pairs consists of all pairs of mappings fromΘ\\Thetato𝒜H\\mathcal\{A\}\_\{H\}and𝒜H\\mathcal\{A\}\_\{H\}to𝒜A\\mathcal\{A\}\_\{A\}\. This space has sizeMHN⋅MAMHM\_\{H\}^\{N\}\\cdot M\_\{A\}^\{M\_\{H\}\}, which is exponential in the game dimensionsNNandMHM\_\{H\}\. To isolate this computational challenge from the coordination challenge, we first consider an idealized*centralized*setting \([Definition˜A\.1](https://arxiv.org/html/2607.08012#A1.Thmtheorem1)\) where a meta\-player jointly chooses both the human’s and the assistant’s policies\. We provide a centralized algorithm withpoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)runtime and prove that it has sublinear\(1−1/e\)\(1\-1/e\)\-assistance regret \([Section˜5](https://arxiv.org/html/2607.08012#S5)\)\. The key insight is a reduction of joint policy optimization in assistance games to maximization of a special subclass of submodular functions—weighted threshold potentials \([Definition˜A\.2](https://arxiv.org/html/2607.08012#A1.Thmtheorem2)\)—over a partition matroid \([Definition˜A\.3](https://arxiv.org/html/2607.08012#A1.Thmtheorem3)\)\. This lets us build upon existing algorithms on online convex optimization for submodular maximizationSalem et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib51)\)\.111While any algorithm for online submodular optimization would be effective here, our choice to build uponSalem et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib51)\)is guided by additional properties we will need for the decentralized setting\. In particular, because this algorithm is based on online convex optimization, we can make it such that the total number of steps where the selected policies switch is sublinear\.Even in this idealized centralized setting, the approximation factor of\(1−1/e\)\(1\-1/e\)is tight without compromising on the computational efficiency\.

Figure 1:Generic algorithms in the centralized setting\(AlgC\)\(\\mathrm\{Alg\}\_\{C\}\)and decentralized setting \(AlgH\\mathrm\{Alg\}\_\{H\}andAlgA\\mathrm\{Alg\}\_\{A\}\)\.AlgC\\mathrm\{Alg\}\_\{C\}\(centralized\) 1:Play\(πH\(t\),πA\(t\)\)\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\)2:Observeθ\(t\)\\theta^\{\(t\)\}3:Receive rewardrt​\(πH\(t\),πA\(t\)\)r\_\{t\}\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\)AlgA\\mathrm\{Alg\}\_\{A\}\(decentralized assistant\) 1:ObserveπH\(t\)​\(θ\(t\)\)\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)2:PlayπA\(t\)\\pi\_\{A\}^\{\(t\)\}3:Receive and seert​\(πH\(t\),πA\(t\)\)r\_\{t\}\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\)AlgH\\mathrm\{Alg\}\_\{H\}\(decentralized human\) 1:Observeθ\(t\)\\theta^\{\(t\)\}2:\(π¯H\(t\),π¯A\(t\)\)←AlgC​\(θ\(1\),…,θ\(t−1\)\)\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\overline\{\\pi\}\_\{A\}^\{\(t\)\}\)\\leftarrow\\mathrm\{Alg\}\_\{C\}\(\\theta^\{\(1\)\},\\ldots,\\theta^\{\(t\-1\)\}\)3:Playπ¯H\(t\)​\(θ\(t\)\)\\overline\{\\pi\}\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)

#### Challenge 2: Coordination through decentralized learning \([Section˜6](https://arxiv.org/html/2607.08012#S6)\)\.

In the actual online assistance game, the human and assistant learn in a decentralized manner\. That is, their strategies must recover the joint optimal without being jointly optimized\. We call this the*coordination*challenge\. We show that given any online algorithm for the centralized setting \(AlgC\\mathrm\{Alg\}\_\{C\}\), and any online algorithm for the assistant’s problem \(AlgA\\mathrm\{Alg\}\_\{A\}\), we can construct an online algorithm in the decentralized setting for the human that overcomes the coordination challenge\. In particular, we decompose the assistance regret of the decentralized pair of policies into the sum of the centralized algorithm’s external regret and a coordination cost that depends on tracking regret ofAlgA\\mathrm\{Alg\}\_\{A\}and the number of switchesAlgC\\mathrm\{Alg\}\_\{C\}makes in its choices\. This is formalized in the following lemma\.

###### Lemma 4\.4\.

Given any online algorithmAlgC\\mathrm\{Alg\}\_\{C\}in the centralized setting, and any online algorithmAlgA\\mathrm\{Alg\}\_\{A\}for the the assistant, there is a \(decentralized\) human algorithmAlgH\\mathrm\{Alg\}\_\{H\}, that for everyδ\>0\\delta\>0, achieve assistance regret of at most

RTα≤RTα,ext​\(AlgC\)\+RTt​r​a​c​k​\(AlgA;ST​\(AlgC;δ\)\)\+δ​T,R^\{\\alpha\}\_\{T\}\\leq R\_\{T\}^\{\\alpha,\\textrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\+R\_\{T\}^\{track\}\(\\mathrm\{Alg\}\_\{A\};S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\delta\)\)\+\\delta T,whereST​\(AlgC;δ\)S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\delta\)is an upper bound on the number of timesAlgC\\mathrm\{Alg\}\_\{C\}switches strategies that holds with probability at least1−δ1\-\\deltaandRTα,e​x​t,RTt​r​a​c​kR^\{\\alpha,ext\}\_\{T\},R^\{track\}\_\{T\}denoteα\\alpha\-approximate\-external and \(exact\)\-tracking regrets, respectively\. Furthermore,AlgH\\mathrm\{Alg\}\_\{H\}, described in Algorithm[1](https://arxiv.org/html/2607.08012#S4.F1), is a simple wrapper around the centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}\.

The decomposition \(proved in[Section˜D\.5](https://arxiv.org/html/2607.08012#A4.SS5)\) guides our algorithm design: we want a centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}with low external regret*and*few switches \(soST​\(AlgC;δ\)S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\delta\)is small\), and an assistant algorithmAlgA\\mathrm\{Alg\}\_\{A\}with low tracking regret\. Both*stability*\(few switches\) and*adaptivity*\(low tracking regret\) are well\-studied notions in the online learning literature\. We exploit the fact that our centralized algorithm of[Proposition˜5\.1](https://arxiv.org/html/2607.08012#S5.Thmtheorem1)is based on online convex optimization to make it*stable*\([Section˜6\.1](https://arxiv.org/html/2607.08012#S6.SS1),[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\), and we construct an efficient adaptive assistant algorithm using the machinery tracking\-regret \([Section˜6\.2](https://arxiv.org/html/2607.08012#S6.SS2)\)\.

## 5Computationally Efficient Algorithms for Centralized Learning in Assistance Games

This section addresses the computational challenge identified in[Section˜4](https://arxiv.org/html/2607.08012#S4)\. We isolate it from the coordination challenge by studying an idealized*centralized*setting in which a meta\-player jointly chooses both the human and assistant policies\. We develop a centralized algorithm that achieves\(1−1/e\)\(1\-1/e\)\-approximate assistance regret at a rate of𝒪​\(T\)\\mathcal\{O\}\\left\(\\sqrt\{T\}\\right\)inpoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time, despite the exponentially large joint policy space\. This algorithm will serve as the building block for the decentralized algorithm in[Section˜6](https://arxiv.org/html/2607.08012#S6)\.

In the centralized online assistance game \([Definition˜A\.1](https://arxiv.org/html/2607.08012#A1.Thmtheorem1)\), a meta\-player chooses a joint policy pair\(πH\(t\),πA\(t\)\)∈ΠH×ΠA\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\)\\in\\Pi\_\{H\}\\times\\Pi\_\{A\}at each round before the realized preferenceθ\(t\)\\theta^\{\(t\)\}is revealed, and receives rewardr​\(πH\(t\),πA\(t\);θ\(t\)\)r\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\};\\theta^\{\(t\)\}\)\. The meta\-player’s external regret in this game—against the best fixed pair\(πH∗,πA∗\)\(\\pi\_\{H\}^\{\*\},\\pi\_\{A\}^\{\*\}\)in hindsight—is exactly the assistance regret \([Definition˜3\.1](https://arxiv.org/html/2607.08012#S3.Thmtheorem1)\), so any low\-external\-regret algorithm in the centralized game yields low assistance regret\.

Our main result for the centralized setting is a tractable algorithm with sublinear\(1−1/e\)\(1\-1/e\)\-approximate assistance regret\.

###### Proposition 5\.1\.

There is apoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time algorithm for the meta\-player in the centralized assistance game \([Definition˜A\.1](https://arxiv.org/html/2607.08012#A1.Thmtheorem1)\), such that the meta\-player’s expected\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-assistance regret is at most𝒪​\(MH​T​log⁡MA\)\\mathcal\{O\}\\left\(M\_\{H\}\\sqrt\{T\\log M\_\{A\}\}\\right\)\.

The main proof idea is a reduction of the assistance game to submodular maximization under matroid constraints, which lets us apply algorithms from prior work\. We next develop this reduction in[Section˜5\.1](https://arxiv.org/html/2607.08012#S5.SS1)\.

### 5\.1A Reduction to Online Submodular Maximization

To derive the reduction, we first represent the policy space as a partition matroid\. Next, we show that the optimization objective over this representation satisfies structural properties that enable tractable online submodular optimization via the algorithms ofSalem et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib51)\)\.

#### Policy space representation\.

We first note that joint optimization over human\-asssistant policy pairs\(πH,πA\)\(\\pi\_\{H\},\\pi\_\{A\}\)reduces to optimization over assistant policies alone\. Given anyπA\\pi\_\{A\}, the meta\-player can pair it with the best\-response human policyπH∗​\(θ\):=arg⁡maxaH⁡r​\(aH,πA​\(aH\);θ\)\\pi\_\{H\}^\{\*\}\(\\theta\):=\\arg\\max\_\{a\_\{H\}\}r\(a\_\{H\},\\pi\_\{A\}\(a\_\{H\}\);\\theta\)\. We represent each assistant policyπA:𝒜H→𝒜A\\pi\_\{A\}:\\mathcal\{A\}\_\{H\}\\to\\mathcal\{A\}\_\{A\}as the set of human\-assistant action pairs\{\(aH,πA​\(aH\)\):aH∈𝒜H\}\\\{\(a\_\{H\},\\pi\_\{A\}\(a\_\{H\}\)\):a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\\\}it induces, and the resulting policy space as a partition matroid\.

###### Definition 5\.2\(Assistance Matroid\)\.

Given an assistance gameGGwith human action space𝒜H\\mathcal\{A\}\_\{H\}and assistant action space𝒜A\\mathcal\{A\}\_\{A\}, define the*assistance matroid*ℳG=\(𝒰G,ℐG\)\\mathcal\{M\}\_\{G\}=\(\\mathcal\{U\}\_\{G\},\\mathcal\{I\}\_\{G\}\)where:

- •𝒰G=𝒜H×𝒜A\\mathcal\{U\}\_\{G\}=\\mathcal\{A\}\_\{H\}\\times\\mathcal\{A\}\_\{A\}\.
- •ℐG=\{S⊆𝒰G:for all​\(aH\(1\),aA\(1\)\),\(aH\(2\),aA\(2\)\)∈S,we have​aH\(1\)≠aH\(2\)\}\\mathcal\{I\}\_\{G\}=\\left\\\{S\\subseteq\\mathcal\{U\}\_\{G\}:\\text\{for all \}\\left\(a\_\{H\}^\{\(1\)\},a\_\{A\}^\{\(1\)\}\\right\),\\left\(a\_\{H\}^\{\(2\)\},a\_\{A\}^\{\(2\)\}\\right\)\\in S,\\text\{ we have \}a\_\{H\}^\{\(1\)\}\\neq a\_\{H\}^\{\(2\)\}\\right\\\}\.

The assistance matroid is a partition matroid \([Definition˜A\.3](https://arxiv.org/html/2607.08012#A1.Thmtheorem3)\) of rankMHM\_\{H\}, with parts𝒰aH=\{aH\}×𝒜A\\mathcal\{U\}\_\{a\_\{H\}\}=\\\{a\_\{H\}\\\}\\times\\mathcal\{A\}\_\{A\}and capacitiesdaH=1d\_\{a\_\{H\}\}=1\([Lemma˜D\.1](https://arxiv.org/html/2607.08012#A4.Thmtheorem1), proved in[Section˜D\.1](https://arxiv.org/html/2607.08012#A4.SS1)\)\.

#### Optimization objective and its structural properties\.

For each preferenceθ\\theta, the*value of assistance function*VθV\_\{\\theta\}maps an independent setII\(equivalently, an assistant policy\) to the reward achieved by pairing it with the best\-response human policy underθ\\theta\. This is the objective function we maximize over the matroid representation of the policy space\.

###### Definition 5\.3\(Value of Assistance Function\)\.

Given an assistance gameGG, the value of assistance function for a human preferenceθ∈Θ\\theta\\in\\Thetais the functionVθ:ℐG→ℝV\_\{\\theta\}:\\mathcal\{I\}\_\{G\}\\to\\mathbb\{R\}defined over independent setsℐG\\mathcal\{I\}\_\{G\}of the assistance matroidℳG=\(𝒰G,ℐG\)\\mathcal\{M\}\_\{G\}=\(\\mathcal\{U\}\_\{G\},\\mathcal\{I\}\_\{G\}\), such thatVθ​\(∅\)=0V\_\{\\theta\}\(\\emptyset\)=0and for all non\-emptyS∈ℐGS\\in\\mathcal\{I\}\_\{G\},

Vθ​\(S\)=max\(aH,aA\)∈S⁡r​\(aH,aA;θ\)\.V\_\{\\theta\}\(S\)=\\max\_\{\(a\_\{H\},a\_\{A\}\)\\in S\}r\(a\_\{H\},a\_\{A\};\\theta\)\.

The following proposition formalizes the reduction: the centralized online assistance game reduces to online maximization of value of assistance functions over the assistance matroid\. The proof is deferred to[Section˜D\.2](https://arxiv.org/html/2607.08012#A4.SS2)\.

###### Proposition 5\.4\.

The centralized online assistance gameGGreduces to an online optimization over the family of value of assistance functionsVθV\_\{\\theta\}defined over independent sets of the assistance matroidℳG\\mathcal\{M\}\_\{G\}\. That is, the following conditions are met

1. 1\.For every independent setI∈ℐGI\\in\\mathcal\{I\}\_\{G\}and preferenceθ∈Θ\\theta\\in\\Theta, there exists a human\-assistant policy pairπH,πA∈ΠH,ΠA\\pi\_\{H\},\\pi\_\{A\}\\in\\Pi\_\{H\},\\Pi\_\{A\}achieving reward at leastVθ​\(I\)V\_\{\\theta\}\(I\)\.
2. 2\.For every assistant policyπA∈ΠA\\pi\_\{A\}\\in\\Pi\_\{A\}, there exists an independent setI∈ℐGI\\in\\mathcal\{I\}\_\{G\}such that for all preferencesθ∈Θ\\theta\\in\\Thetaand all human policiesπH∈ΠH\\pi\_\{H\}\\in\\Pi\_\{H\}, the reward the policy pairπH,πA∈ΠH,ΠA\\pi\_\{H\},\\pi\_\{A\}\\in\\Pi\_\{H\},\\Pi\_\{A\}achieves is at mostVθ​\(I\)V\_\{\\theta\}\(I\)\.

The value of assistance function further satisfies structural properties that enable tractable online optimization via the algorithms ofSalem et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib51)\)\.

###### Lemma 5\.5\(Structural properties ofVθV\_\{\\theta\}, informal\)\.

For every preferenceθ∈Θ\\theta\\in\\Theta, the value of assistance functionVθV\_\{\\theta\}is a weighted threshold potential \([Definition˜A\.2](https://arxiv.org/html/2607.08012#A1.Thmtheorem2)\), and its concave relaxation \([Definition˜A\.4](https://arxiv.org/html/2607.08012#A1.Thmtheorem4)\) is11\-Lipschitz\.

The formal statements \([Lemmas˜D\.2](https://arxiv.org/html/2607.08012#A4.Thmtheorem2)and[D\.3](https://arxiv.org/html/2607.08012#A4.Thmtheorem3)\) and proofs are deferred to[Section˜D\.3](https://arxiv.org/html/2607.08012#A4.SS3)\.

#### Centralized Algorithm\.

The reduction lets us apply the Randomized\-Augmented OCO \(RAOCO\) algorithm ofSalem et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib51)\)directly\. RAOCO reduces online submodular maximization of weighted threshold potentials to online convex optimization\. It runs a standard OCO algorithm \(e\.g\., Follow the Perturbed Leader or Online Mirror Descent\) on concave relaxations of the objectives over the convex hull of the strategy space, then rounds each iterate back to an integral point\. The weighted threshold and Lipschitz properties ofVθV\_\{\\theta\}ensure that the rounding error is small, yielding the bound in[Proposition˜5\.1](https://arxiv.org/html/2607.08012#S5.Thmtheorem1)\.

The full proof, which combines[Proposition˜5\.4](https://arxiv.org/html/2607.08012#S5.Thmtheorem4)and the structural properties with the regret guarantees of RAOCO \(restated in[Proposition˜E\.2](https://arxiv.org/html/2607.08012#A5.Thmtheorem2)\), is deferred to[Section˜D\.4](https://arxiv.org/html/2607.08012#A4.SS4)\.

## 6Decentralized Learning in Assistance Games: Stable and Adaptive Algorithms

In this section, we move beyond the idealized centralized setting and consider the decentralized setting\.[Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)forms the backbone for building on top of the algorithm design in the centralized setting\. It shows how to construct an algorithm for the humanAlgH\\mathrm\{Alg\}\_\{H\}based on a centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}via the construction in[Figure˜1](https://arxiv.org/html/2607.08012#S4.F1)\. Additionally, it identifies stability of the centralized algorithm, in the form of having low switches, and adaptivity of the assistant’s algorithmAlgA\\mathrm\{Alg\}\_\{A\}, in the form of having low tracking regret, as sufficient properties for yielding low assistance regret\. Directed by this, we will construct a stable centralized algorithm that has low external regret while making few switches in[Section˜6\.1](https://arxiv.org/html/2607.08012#S6.SS1)and an adaptive algorithm for the assistant having low tracking regret in[Section˜6\.2](https://arxiv.org/html/2607.08012#S6.SS2)\. In[Section˜6\.3](https://arxiv.org/html/2607.08012#S6.SS3), we put together these components to prove the regret guarantees provided by our main theorems\.

### 6\.1The Stable Centralized Algorithm

In this section, we design a stable centralized algorithm that makes a small number of switches\. We build on the centralized algorithm designed in[Section˜5](https://arxiv.org/html/2607.08012#S5)\.

###### Proposition 6\.1\.

There is apoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time algorithm for the centralized assistance game that achieves expected\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-approximate assistance regret𝒪​\(MA​MH​T\)\\mathcal\{O\}\\left\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\\right\)and makes at mostST∈O​\(MA​MH​T​log⁡\(T/δ\)\)S\_\{T\}\\in O\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\log\(T/\\delta\)\)switches with probability at least1−δ1\-\\delta\.

###### Proof sketch of[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\.

Recall that the centralized algorithm of[Section˜5](https://arxiv.org/html/2607.08012#S5)takes an online convex optimization algorithm and rounds the output of the OCO algorithm to the strategy space of the assistance game\. To make this algorithm stable, we account for two sources of switches: switches in the OCO algorithm’s iterates and switches in the rounding step\.

#### Stable OCO\.

Online convex optimization with few switches has been studied by previous work\(Agarwal et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib1); Anava et al\.,[2015](https://arxiv.org/html/2607.08012#bib.bib4); Sherman and Koren,[2021](https://arxiv.org/html/2607.08012#bib.bib54)\)\. We use the Private Continuous Online Multiplicative Weights with Euclidean Regularization \(POMER\) algorithm ofAgarwal et al\. \([2024](https://arxiv.org/html/2607.08012#bib.bib1)\)as the inner OCO optimizer, POMER requires only that the losses be convex and Lipschitz, conditions that hold for the value\-of\-assistance concave relaxationV~θ\\tilde\{V\}\_\{\\theta\}\([Lemma˜D\.3](https://arxiv.org/html/2607.08012#A4.Thmtheorem3)\)\.

#### Coupled rounding\.

Even if the OCO algorithm’s iterates are stable, the rounded outputs may not be, since the rounding algorithm used \(like swap rounding or randomized pipage rounding\(Chekuri et al\.,[2010](https://arxiv.org/html/2607.08012#bib.bib10)\)\) is randomized\. So even though the OCO algorithm returns the same solution in different rounds, the randomness in the rounding can lead to different rounded outputs\. To overcome this, we couple the randomness of the rounding step across rounds\. That is, the same source of randomness is used for rounding across all rounds\. Doing this does not change the marginal distribution of the rounded output\. In particular, it does not change the expected reward of the rounded output\. So the property on the expected reward of the rounded output that is used in the regret analysis \(the property in[Proposition˜E\.1](https://arxiv.org/html/2607.08012#A5.Thmtheorem1)\) is preserved\. This algorithm is described in[Algorithm˜2](https://arxiv.org/html/2607.08012#alg2)\.

The full proof, which combines the regret guarantee of the underlying stable OCO algorithm with the switch\-preserving property of coupled rounding, is given in[Section˜D\.6](https://arxiv.org/html/2607.08012#A4.SS6)\. ∎

### 6\.2The Adaptive Assistant Algorithm

We now design a computationally efficient assistant algorithm with low tracking regret relative to the policies chosen by the stable centralized algorithm\. Tracking regret is a well\-studied notion in online learning, with standard algorithms achieving𝒪​\(T​p\)\\mathcal\{O\}\\left\(\\sqrt\{Tp\}\\right\)regret against any sequence of reward functions overppsegments\. We lift these into an assistant algorithm with low tracking regret over the assistant policy spaceΠA\\Pi\_\{A\}\.

###### Proposition 6\.2\.

There is apoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time assistant algorithmAlgA\\mathrm\{Alg\}\_\{A\}whose tracking regret overppsegments satisfiesRTtrack​\(AlgA;p\)∈𝒪​\(MH​MA​T​p​log⁡\(MA​T\)\)R^\{\\mathrm\{track\}\}\_\{T\}\(\\mathrm\{Alg\}\_\{A\};\\,p\)\\;\\in\\;\\mathcal\{O\}\\left\(M\_\{H\}\\sqrt\{M\_\{A\}Tp\\log\(M\_\{A\}T\)\}\\right\)\.

###### Proof sketch of[Proposition˜6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2)\.

We constructAlgA\\mathrm\{Alg\}\_\{A\}from an off\-the\-shelf tracking\-regret minimizerAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}\(e\.g\. Fixed\-Share\(Herbster and Warmuth,[1998](https://arxiv.org/html/2607.08012#bib.bib28); Cesa\-Bianchi et al\.,[2012](https://arxiv.org/html/2607.08012#bib.bib8)\)\) used as a black box\. The assistant maintainsMHM\_\{H\}independent copies ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}, one per human actionaH∈𝒜Ha\_\{H\}\\in\\mathcal\{A\}\_\{H\}, each optimizing over the assistant’s action space𝒜A\\mathcal\{A\}\_\{A\}\. In roundtt, after observingaH\(t\)a\_\{H\}^\{\(t\)\}, the assistant plays the action selected by the copy associated withaH\(t\)a\_\{H\}^\{\(t\)\}and updates only that copy with the observed reward\. The assistant’s tracking regret then decomposes as the sum of the tracking regrets of theMHM\_\{H\}copies ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}, which yields the claimed bound after substituting the standard Fixed\-Share tracking\-regret guarantee \(restated as[Theorem˜E\.5](https://arxiv.org/html/2607.08012#A5.Thmtheorem5)in[Section˜E\.3](https://arxiv.org/html/2607.08012#A5.SS3)\)\. The full proof appears in[Section˜D\.7](https://arxiv.org/html/2607.08012#A4.SS7)\.

∎

### 6\.3Putting It All Together

We now combine the stable centralized algorithm of[Section˜6\.1](https://arxiv.org/html/2607.08012#S6.SS1)and the adaptive assistant algorithm of[Section˜6\.2](https://arxiv.org/html/2607.08012#S6.SS2)via the stable–adaptive decomposition of[Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)to prove our main theorems\. Full proofs are in[Sections˜D\.8](https://arxiv.org/html/2607.08012#A4.SS8)and[D\.9](https://arxiv.org/html/2607.08012#A4.SS9)\.

#### Proof idea for[Theorem˜4\.1](https://arxiv.org/html/2607.08012#S4.Thmtheorem1)\.

The decentralized algorithms here are built entirely from general\-purpose no\-regret components: the human algorithmAlgH\\mathrm\{Alg\}\_\{H\}is derived \(via[Figure˜1](https://arxiv.org/html/2607.08012#S4.F1)\) from the stable centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}of[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1), and the assistant runs the tracking\-regret algorithmAlgA\\mathrm\{Alg\}\_\{A\}of[Proposition˜6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2)\. SubstitutingAlgC\\mathrm\{Alg\}\_\{C\}’s external regret and high\-probability switching bound together withAlgA\\mathrm\{Alg\}\_\{A\}’s tracking regret into the stable–adaptive decomposition \([Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)\) yields the claimed𝒪​\(MH5/4​MA3/4​log⁡\(MA​T\)​T3/4\+MA​MH​T\)\\mathcal\{O\}\\left\(M\_\{H\}^\{5/4\}M\_\{A\}^\{3/4\}\\log\(M\_\{A\}T\)\\,T^\{3/4\}\+M\_\{A\}M\_\{H\}\\sqrt\{T\}\\right\)bound; the full calculation appears in[Section˜D\.8](https://arxiv.org/html/2607.08012#A4.SS8)\. Note that this construction, and the assistant’s algorithm in particular, requires minimal knowledge of the assistance game structure\. The assistant merely needs to know its action space and its observed reward\.

#### Proof idea for[Theorem˜4\.2](https://arxiv.org/html/2607.08012#S4.Thmtheorem2)\.

We use algorithms more tailored to the assistance game for a𝒪~​\(T\)\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{T\}\\right\)rate, optimal inTTup to logarithmic factors\. We allow the human and assistant some initial synchronization in the form of a shared mappingϕ:𝒜H∗→ΠA\\phi:\\mathcal\{A\}\_\{H\}^\{\*\}\\to\\Pi\_\{A\}from human action sequences to assistant policies, agreed on before the game begins\. The mappingϕ\\philets the human signal a policy switch and encode the new assistant policy via a string of actions\. The assistant decodes this string usingϕ\\phiand then plays the new policy directly, bypassing further exploration and decreasing its tracking regret\. Plugging this into the stable–adaptive decomposition \([Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)\) yields the claimed𝒪~​\(T\)\\tilde\{\\mathcal\{O\}\}\\left\(\\sqrt\{T\}\\right\)bound\. The full proof, including details of how the shared mapping is used, appears in[Section˜D\.9](https://arxiv.org/html/2607.08012#A4.SS9)\.

## 7Discussion

Our framework identifies two broad components useful for learning to cooperate under information asymmetry\. The first is*submodularity*as a source of tractable approximation\. This points to the usefulness of methods that exploit submodular structure—such as greedy algorithms that measure the marginal improvement of adding actions to communicate or steer\. The second component is*stability*and*adaptivity*as properties of the dynamics of interaction\. Our decomposition \([Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)\) shows that algorithms satisfying these standard online\-learning notions plug in directly as building blocks for learning algorithms in these settings\.

#### Limitations and Extensions\.

Our regret bounds are tight inTTbut the dependence on the action\-space sizesMHM\_\{H\}andMAM\_\{A\}may be loose; determining the optimal scaling is an open question\. The optimal𝒪​\(T\)\\mathcal\{O\}\\left\(\\sqrt\{T\}\\right\)rate also relies on an initial shared encodingϕ:𝒜H∗→ΠA\\phi:\\mathcal\{A\}\_\{H\}^\{\*\}\\to\\Pi\_\{A\}, and it is open whether the same rate is achievable without such pre\-game synchronization\. Finally, it would be interesting to extend the framework to richer interaction settings such as long horizon interactions under a fixed preference state, or two\-sided information asymmetry in which the assistant also holds private information\.

## Acknowledgments

This work was supported in part by the National Science Foundation under grant CCF\-2145898, by the Office of Naval Research under grant N00014\-24\-1\-2159, by a Google Research Scholar Award, an Alfred P\. Sloan fellowship, and a Schmidt Science AI2050 fellowship, and by a gift from Coefficient Giving \(formerly Open Philanthropy\) to support the work of the Center for Human\-Compatible AI at Berkeley\. We also wish to acknowledge funding by the European Union \(ERC\-2022\-SYG\-OCEAN\-101071601\)\. Views and opinions expressed are however those of the author\(s\) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency\. Neither the European Union nor the granting authority can be held responsible for them\.

## References

- Agarwal et al\. \[2024\]Naman Agarwal, Satyen Kale, Karan Singh, and Abhradeep Guha Thakurta\.Improved differentially private and lazy online convex optimization: Lower regret without smoothness requirements\.In*Proceedings of the 41st International Conference on Machine Learning*, volume 235 of*Proceedings of Machine Learning Research*, pages 343–361\. PMLR, 2024\.
- Altschuler and Talwar \[2018\]Jason Altschuler and Kunal Talwar\.Online learning over a finite action set with limited switching\.In*Conference On Learning Theory*, pages 1569–1573\. PMLR, 2018\.
- Alur et al\. \[2024\]Rohan Alur, Manish Raghavan, and Devavrat Shah\.Human expertise in algorithmic prediction\.*Advances in Neural Information Processing Systems*, 37:138088–138129, 2024\.
- Anava et al\. \[2015\]Oren Anava, Elad Hazan, and Shie Mannor\.Online learning for adversaries with memory: price of past mistakes\.In*Advances in Neural Information Processing Systems*, pages 784–792, 2015\.
- Athey et al\. \[2020\]Susan C Athey, Kevin A Bryan, and Joshua S Gans\.The allocation of decision authority to human and artificial intelligence\.In*AEA Papers and Proceedings*, volume 110, pages 80–84\. American Economic Association 2014 Broadway, Suite 305, Nashville, TN 37203, 2020\.
- Bansal et al\. \[2021\]Gagan Bansal, Tongshuang Wu, Joyce Zhou, Raymond Fok, Besmira Nushi, Ece Kamar, Marco Tulio Ribeiro, and Daniel Weld\.Does the whole exceed its parts? the effect of ai explanations on complementary team performance\.In*Proceedings of the 2021 CHI conference on human factors in computing systems*, pages 1–16, 2021\.
- Brown et al\. \[2024\]William Brown, Jon Schneider, and Kiran Vodrahalli\.Is learning in games good for the learners?*Advances in Neural Information Processing Systems*, 36, 2024\.
- Cesa\-Bianchi et al\. \[2012\]Nicolo Cesa\-Bianchi, Pierre Gaillard, Gábor Lugosi, and Gilles Stoltz\.Mirror descent meets fixed share \(and feels no regret\)\.*Advances in Neural Information Processing Systems*, 25, 2012\.
- Chaabouni et al\. \[2022\]Rahma Chaabouni, Florian Strub, Florent Altché, Eugene Tarassov, Corentin Tallec, Elnaz Davoodi, Kory Wallace Mathewson, Olivier Tieleman, Angeliki Lazaridou, and Bilal Piot\.Emergent communication at scale\.In*International conference on learning representations*, 2022\.
- Chekuri et al\. \[2010\]Chandra Chekuri, Jan Vondrák, and Rico Zenklusen\.Dependent randomized rounding via exchange properties of combinatorial structures\.In*2010 IEEE 51st Annual Symposium on Foundations of Computer Science*, pages 575–584\. IEEE, 2010\.
- Chu and Halpern \[2001\]Francis Chu and Joseph Halpern\.On the np\-completeness of finding an optimal strategy in games with common payoffs\.*International Journal of Game Theory*, 30:99–106, 2001\.
- Collina et al\. \[2026\]Natalie Collina, Ira Globus\-Harris, Surbhi Goel, Varun Gupta, Aaron Roth, and Mirah Shi\.Collaborative prediction: Tractable information aggregation via agreement\.In*Proceedings of the 2026 Annual ACM\-SIAM Symposium on Discrete Algorithms \(SODA\)*, pages 4712–4798\. SIAM, 2026\.
- Conitzer and Sandholm \[2006\]Vincent Conitzer and Tuomas Sandholm\.Computing the optimal strategy to commit to\.In*Proceedings of the 7th ACM conference on Electronic commerce*, pages 82–90, 2006\.
- Daniely et al\. \[2015\]Amit Daniely, Alon Gonen, and Shai Shalev\-Shwartz\.Strongly adaptive online learning\.In*International Conference on Machine Learning*, pages 1405–1411\. PMLR, 2015\.
- Donahue et al\. \[2022\]Kate Donahue, Alexandra Chouldechova, and Krishnaram Kenthapadi\.Human\-algorithm collaboration: Achieving complementarity and avoiding unfairness\.In*Proceedings of the 2022 ACM Conference on Fairness, Accountability, and Transparency*, pages 1639–1656, 2022\.
- Feige \[1998\]Uriel Feige\.A threshold of ln n for approximating set cover\.*Journal of the ACM \(JACM\)*, 45\(4\):634–652, 1998\.
- Fern et al\. \[2014\]Alan Fern, Sriraam Natarajan, Kshitij Judah, and Prasad Tadepalli\.A decision\-theoretic model of assistance\.*Journal of Artificial Intelligence Research*, 50:71–104, 2014\.
- Foerster et al\. \[2016\]Jakob N Foerster, Yannis M Assael, Nando de Freitas, and Shimon Whiteson\.Learning to communicate to solve riddles with deep distributed recurrent q\-networks\.*arXiv preprint arXiv:1602\.02672*, 2016\.
- Franke \[2009a\]Michael Franke\.Interpretation of optimal signals\.*New perspectives on games and interaction*, pages 297–310, 2009a\.
- Franke \[2009b\]Michael Franke\.*Signal to act: Game theory in pragmatics*\.University of Amsterdam, 2009b\.
- Gilboa and Zemel \[1989\]Itzhak Gilboa and Eitan Zemel\.Nash and correlated equilibria: Some complexity considerations\.*Games and Economic Behavior*, 1\(1\):80–93, 1989\.
- Green and Chen \[2019\]Ben Green and Yiling Chen\.The principles and limits of algorithm\-in\-the\-loop decision making\.*Proceedings of the ACM on human\-computer interaction*, 3\(CSCW\):1–24, 2019\.
- Greenwood et al\. \[2025\]Sophie Greenwood, Karen Levy, Solon Barocas, Hoda Heidari, and Jon Kleinberg\.Designing algorithmic delegates: The role of indistinguishability in human\-ai handoff\.In*Proceedings of the 26th ACM Conference on Economics and Computation*, pages 306–336, 2025\.
- Hadfield\-Menell et al\. \[2016\]Dylan Hadfield\-Menell, Stuart J Russell, Pieter Abbeel, and Anca Dragan\.Cooperative inverse reinforcement learning\.*Advances in neural information processing systems*, 29, 2016\.
- Hadfield\-Menell et al\. \[2017\]Dylan Hadfield\-Menell, Anca D Dragan, Pieter Abbeel, and Stuart Russell\.The off\-switch game\.In*AAAI Workshops*, 2017\.
- Havrylov and Titov \[2017\]Serhii Havrylov and Ivan Titov\.Emergence of language with multi\-agent games: Learning to communicate with sequences of symbols\.*Advances in neural information processing systems*, 30, 2017\.
- Hazan and Seshadhri \[2007\]Elad Hazan and Comandur Seshadhri\.Adaptive algorithms for online decision problems\.In*Electronic colloquium on computational complexity \(ECCC\)*, volume 14, 2007\.
- Herbster and Warmuth \[1998\]Mark Herbster and Manfred K Warmuth\.Tracking the best expert\.*Machine learning*, 32\(2\):151–178, 1998\.
- Ho et al\. \[1972\]Yu\-Chi Ho et al\.Team decision theory and information structures in optimal control problems–part i\.*IEEE Transactions on Automatic control*, 17\(1\):15–22, 1972\.
- Jacob et al\. \[2023\]Athul Paul Jacob, Gabriele Farina, and Jacob Andreas\.Regularized conventions: Equilibrium computation as a model of pragmatic reasoning\.*arXiv preprint arXiv:2311\.09712*, 2023\.
- Jäger \[2007\]Gerhard Jäger\.Game dynamics connects semantics and pragmatics\.In*Game theory and linguistic meaning*, pages 103–117\. Brill, 2007\.
- Jäger \[2012\]Gerhard Jäger\.Game theory in semantics and pragmatics\.*Semantics: An international handbook of natural language meaning*, 3:2487–2516, 2012\.
- Kapralov et al\. \[2013\]Michael Kapralov, Ian Post, and Jan Vondrák\.Online submodular welfare maximization: Greedy is optimal\.In*Proceedings of the twenty\-fourth annual ACM\-SIAM symposium on Discrete algorithms*, pages 1216–1225\. SIAM, 2013\.
- Kim and Oh \[2021\]Jooyeon Kim and Alice Oh\.Emergent communication under varying sizes and connectivities\.*Advances in Neural Information Processing Systems*, 34:17579–17591, 2021\.
- Kirby \[2002\]Simon Kirby\.Natural language from artificial life\.*Artificial life*, 8\(2\):185–215, 2002\.
- Kirby et al\. \[2014\]Simon Kirby, Tom Griffiths, and Kenny Smith\.Iterated learning and the evolution of language\.*Current opinion in neurobiology*, 28:108–114, 2014\.
- Laidlaw et al\. \[2025\]Cassidy Laidlaw, Eli Bronstein, Timothy Guo, Dylan Feng, Lukas Berglund, Justin Svegliato, Stuart Russell, and Anca Dragan\.Assistancezero: Scalably solving assistance games\.In*Forty\-second International Conference on Machine Learning*, 2025\.URL[https://openreview\.net/forum?id=b9hVMJi0t2](https://openreview.net/forum?id=b9hVMJi0t2)\.
- Lazaridou and Baroni \[2020\]Angeliki Lazaridou and Marco Baroni\.Emergent multi\-agent communication in the deep learning era\.*arXiv preprint arXiv:2006\.02419*, 2020\.
- Lazaridou et al\. \[2016\]Angeliki Lazaridou, Alexander Peysakhovich, and Marco Baroni\.Multi\-agent cooperation and the emergence of \(natural\) language\.*arXiv preprint arXiv:1612\.07182*, 2016\.
- Letchford et al\. \[2009\]Joshua Letchford, Vincent Conitzer, and Kamesh Munagala\.Learning and approximating the optimal strategy to commit to\.In*Algorithmic Game Theory: Second International Symposium, SAGT 2009, Paphos, Cyprus, October 18\-20, 2009\. Proceedings 2*, pages 250–262\. Springer, 2009\.
- Li and Bowling \[2019\]Fushan Li and Michael Bowling\.Ease\-of\-teaching and language structure from emergent communication\.*Advances in neural information processing systems*, 32, 2019\.
- Lovász and Vempala \[2007\]László Lovász and Santosh Vempala\.The geometry of logconcave functions and sampling algorithms\.*Random Structures & Algorithms*, 30\(3\):307–358, 2007\.
- Mahajan and Mannan \[2016\]Aditya Mahajan and Mehnaz Mannan\.Decentralized stochastic control\.*Annals of Operations Research*, 241\(1\):109–126, 2016\.
- Malik et al\. \[2018\]Dhruv Malik, Malayandi Palaniappan, Jaime Fisac, Dylan Hadfield\-Menell, Stuart Russell, and Anca Dragan\.An efficient, generalized bellman update for cooperative inverse reinforcement learning\.In*International Conference on Machine Learning*, pages 3394–3402\. PMLR, 2018\.
- Malikopoulos \[2022\]Andreas A Malikopoulos\.On team decision problems with nonclassical information structures\.*IEEE Transactions on Automatic Control*, 68\(7\):3915–3930, 2022\.
- Nayyar et al\. \[2013\]Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis\.Decentralized stochastic control with partial history sharing: A common information approach\.*IEEE Transactions on Automatic Control*, 58\(7\):1644–1658, 2013\.
- Peng et al\. \[2019\]Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo\.Learning optimal strategies to commit to\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, volume 33, pages 2149–2156, 2019\.
- Radner \[1962\]Roy Radner\.Team decision problems\.*The Annals of Mathematical Statistics*, 33\(3\):857–881, 1962\.
- Ren et al\. \[2019\]Yi Ren, Shangmin Guo, Serhii Havrylov, Shay Cohen, and Simon Kirby\.Enhance the compositionality of emergent language by iterated learning\.In*3rd NeurIPS Workshop on Emergent Communication \(EmeCom@ NeurIPS 2019\)\. URL https://papers\. nips\. cc/book/advances\-in\-neural\-information\-processing\-systems\-32\-2019*, 2019\.
- Rita et al\. \[2020\]Mathieu Rita, Rahma Chaabouni, and Emmanuel Dupoux\." lazimpa": Lazy and impatient neural agents learn to communicate efficiently\.*arXiv preprint arXiv:2010\.01878*, 2020\.
- Salem et al\. \[2024\]Tareq Si Salem, Gözde Özcan, Iasonas Nikolaou, Evimaria Terzi, and Stratis Ioannidis\.Online submodular maximization via online convex optimization\.In*Proceedings of the AAAI Conference on Artificial Intelligence*, volume 38, pages 15038–15046, 2024\.
- Shah et al\. \[2020\]Rohin Shah, Pedro Freire, Neel Alex, Rachel Freedman, Dmitrii Krasheninnikov, Lawrence Chan, Michael D Dennis, Pieter Abbeel, Anca Dragan, and Stuart Russell\.Benefits of assistance over reward learning, 2020\.
- Shalev\-Shwartz et al\. \[2012\]Shai Shalev\-Shwartz et al\.Online learning and online convex optimization\.*Foundations and Trends® in Machine Learning*, 4\(2\):107–194, 2012\.
- Sherman and Koren \[2021\]Uri Sherman and Tomer Koren\.Lazy oco: Online convex optimization on a switching budget\.In*Conference on Learning Theory*, pages 3972–3988\. PMLR, 2021\.
- Steyvers et al\. \[2022\]Mark Steyvers, Heliodoro Tejeda, Gavin Kerrigan, and Padhraic Smyth\.Bayesian modeling of human–ai complementarity\.*Proceedings of the National Academy of Sciences*, 119\(11\):e2111547119, 2022\.
- Trapa and Nowak \[2000\]Peter E Trapa and Martin A Nowak\.Nash equilibria for an evolutionary language game\.*Journal of mathematical biology*, 41\(2\):172–188, 2000\.
- Wilder et al\. \[2020\]Bryan Wilder, Eric Horvitz, and Ece Kamar\.Learning to complement humans\.*arXiv preprint arXiv:2005\.00582*, 2020\.
- Zrnic et al\. \[2021\]Tijana Zrnic, Eric Mazumdar, Shankar Sastry, and Michael Jordan\.Who leads and who follows in strategic classification?*Advances in Neural Information Processing Systems*, 34:15257–15269, 2021\.

## Appendix AExtended Model and Preliminaries

This appendix presents the two special subclasses of submodular functions and matroids that arise in our reduction of assistance games, together with the concave relaxation we use to optimize over them\. We also state the formal definition of the centralized online assistance game referenced in[Section˜5](https://arxiv.org/html/2607.08012#S5)\.

#### Centralized online assistance game\.

###### Definition A\.1\(Centralized online assistance game\)\.

The centralized online assistance game is a repeated game between nature and a meta\-player who controls both the assistant and human\. At every roundtt, both players take actions simultaneously\.222This means the meta\-player chooses a pair of actions for the human and assistant without having access to the realized state\. We do this to make the idealized setting serve as a building block for the decentralized setting where the assistant must choose a policy without having access to the realized state\.That is, at the start of the interaction, nature chooses a sequence of preferencesθ\(1\),⋯,θ\(T\)∈Θ\\theta^\{\(1\)\},\\cdots,\\theta^\{\(T\)\}\\in\\Theta\. At every iteration, the meta\-player chooses a pair of policies\(πH\(t\),πA\(t\)\)\\left\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\\right\), then the realized preferenceθ\(t\)\\theta^\{\(t\)\}is revealed to the meta\-player, and the meta\-player receives a rewardr​\(πH\(t\),πA\(t\);θ\(t\)\)r\\left\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\};\\theta^\{\(t\)\}\\right\)\.

#### Weighted threshold potentials\.

A useful subclass of submodular functions consists of those that can be written as a sum of capped linear functions\.

###### Definition A\.2\(Weighted Threshold Potential\)\.

Fix a set of elements𝒰\\mathcal\{U\}\. A set functionggover𝒰\\mathcal\{U\}ismodularwhen each elementi∈𝒰i\\in\\mathcal\{U\}is associated with a weightwiw\_\{i\}such thatg​\(S\)=∑j∈Swjg\(S\)=\\sum\_\{j\\in S\}w\_\{j\}\. A set functionffover𝒰\\mathcal\{U\}is athreshold potential function, also known as abudget\-additiveset function, when

f​\(S\)=min⁡\{b,g​\(S\)\}f\(S\)=\\min\\\{b,g\(S\)\\\}for someb∈ℝb\\in\\mathbb\{R\}and some monotone modular functiongg\. A set functionffover𝒰\\mathcal\{U\}is aweighted threshold potentialwhen it is a non\-negative linear combination of threshold potential functions\.

All weighted threshold potentials are submodular\[Salem et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]\.

#### Partition matroids\.

A useful subclass of matroids in our setting is the partition matroid: the set of policies in an assistance game forms a matroid of this form\.

###### Definition A\.3\(Partition Matroids\)\.

A matroid\(𝒰,ℐ\)\(\\mathcal\{U\},\\mathcal\{I\}\)is apartition matroidwhen there exists somek∈ℕk\\in\\mathbb\{N\}, a partition of𝒰\\mathcal\{U\}into subsets𝒰1,…,𝒰k\\mathcal\{U\}\_\{1\},\\dots,\\mathcal\{U\}\_\{k\}, and integersd1,…,dkd\_\{1\},\\dots,d\_\{k\}such that a setIIis independent if and only if

\|I∩𝒰i\|≤di\.\\left\|I\\cap\\mathcal\{U\}\_\{i\}\\right\|\\leq d\_\{i\}\.

#### Concave relaxation\.

To optimize over the space of weighted threshold potential functions, we followSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\], which runs an online convex optimization algorithm on a concave relaxation of these functions\.

###### Definition A\.4\(Concave relaxation of weighted threshold potentials\)\.

Given a weighted threshold potentialf​\(S\)=∑ℓ=1Lcℓ​min⁡\{bℓ,∑j∈Swℓ,j\}f\(S\)=\\sum\_\{\\ell=1\}^\{L\}c\_\{\\ell\}\\min\\\{b\_\{\\ell\},\\sum\_\{j\\in S\}w\_\{\\ell,j\}\\\}defined over someℐ⊆2𝒰\\mathcal\{I\}\\subseteq 2^\{\\mathcal\{U\}\}, its*concave relaxation*f~:\[0,1\]\|𝒰\|→ℝ\\tilde\{f\}:\[0,1\]^\{\|\\mathcal\{U\}\|\}\\to\\mathbb\{R\}is

f~​\(𝐲\)=∑ℓ=1Lcℓ​min⁡\{bℓ,∑j∈𝒰wℓ,j​yj\}\.\\tilde\{f\}\(\\mathbf\{y\}\)=\\sum\_\{\\ell=1\}^\{L\}c\_\{\\ell\}\\min\\left\\\{b\_\{\\ell\},~\\sum\_\{j\\in\\mathcal\{U\}\}w\_\{\\ell,j\}\\,y\_\{j\}\\right\\\}\.This function is concave, since eachmin⁡\{bℓ,⋅\}\\min\\\{b\_\{\\ell\},\\cdot\\\}applied to an affine function is concave, and a positive linear combination of concave functions is concave\. Moreover,f~\\tilde\{f\}agrees withffon integral points:f~​\(𝟙S\)=f​\(S\)\\tilde\{f\}\(\\mathds\{1\}\_\{S\}\)=f\(S\)for allS∈ℐS\\in\\mathcal\{I\}\.

## Appendix BAn Adaptive Nature Player Is Too Powerful

A key assumption in this work is that nature cannot adaptively pick preferences based on the choices of the human and assistant\. Nature becomes too powerful otherwise, removing any hope the learners have of achieving sub\-linear regret\. This is analogous to results in the prediction from experts with switching costs literature, where the learner must suffer linear regret with an adaptive adversary\[Altschuler and Talwar,[2018](https://arxiv.org/html/2607.08012#bib.bib2)\]\.

Nature’s strategy will be to exploit the fact that the human and assistant play moves that are uncorrelated given the history of the game, which nature also has access to\. By being adaptive, nature can exploit uncoordinated agents by taking advantage of the fact that it is impossible to randomize over best\-response pairs in a way that beats an adaptive nature player when actions are independently chosen\.

We will prove an adaptive nature player is too powerful, even for a very simple and restricted class of assistance games\. Consider the class of games where the assistant’s action set equals the set of preferences, and the agents only get a reward when the assistant can reproduce the human’s preference\. The human’s action has no effect on the reward, and serves only to signal the preference to the assistant\. Even on such simple games, when nature can adversarially choose rewards, the agents must suffer linear regret\.

First, we prove a lower bound when the human has one less action than the number of preferences, so there does not exist a perfect signaling scheme the human can use to exactly reveal their preferences\.

###### Lemma B\.1\.

When nature is adaptive, there exist assistance games whereN≥3N\\geq 3andMH=N−1M\_\{H\}=N\-1, such that any learning algorithm must achieve a regret of at leastN−22​N⋅T\\frac\{N\-2\}\{2N\}\\cdot T\.

###### Proof\.

Consider the following assistance game\. The set of preferences is an arbitrary setΘ\\Thetaof sizeNN, the set of human actions is an arbitrary set𝒜H\\mathcal\{A\}\_\{H\}of sizeN−1N\-1, and the set of assistant actions is the set of preferences𝒜A=Θ\\mathcal\{A\}\_\{A\}=\\Theta\. The reward function is defined asr​\(aH,θ′;θ\)=𝟙​\(θ=θ′\)r\(a\_\{H\},\\theta^\{\\prime\};\\theta\)=\\mathds\{1\}\(\\theta=\\theta^\{\\prime\}\)\.

First we will lower bound the utility of the optimal human and assistant strategy in hindsight\. Notice that regardless of the preferences chosen by nature, there must always exist a human\-assistant policy pair that achievesN−1N​T\\frac\{N\-1\}\{N\}Tutility in hindsight\. Indeed, letθ\(1\),…,θ\(T\)\\theta^\{\(1\)\},\\dots,\\theta^\{\(T\)\}be the sequence of preferences played by the adversary\. There must exist a preferenceθ\\thetathat appears at mostTN\\frac\{T\}\{N\}times\. The rest of the states must appear at leastN−1N⋅T\\frac\{N\-1\}\{N\}\\cdot Ttimes\. LetπH\\pi\_\{H\}be the human policy that assigns to each of these preferences a unique one of theN−1N\-1messages, andπA\\pi\_\{A\}be the robot policy that reverses this\. This correctly recovers the state whenθ\\thetadoes not appear, so achieves a utility of at leastN−1N⋅T\\frac\{N\-1\}\{N\}\\cdot T\.

Now we will lower bound the utility the agents can achieve during the learning process\. On stepttover theTTsteps, letℋt=\(θ\(1\),πH\(1\),πA\(1\),…,θ\(t−1\),πH\(t−1\),πA\(t−1\)\)\\mathcal\{H\}\_\{t\}=\\left\(\\theta^\{\(1\)\},\\pi\_\{H\}^\{\(1\)\},\\pi\_\{A\}^\{\(1\)\},\\dots,\\theta^\{\(t\-1\)\},\\pi\_\{H\}^\{\(t\-1\)\},\\pi\_\{A\}^\{\(t\-1\)\}\\right\)be the history of preferences, human policies, and assistant policies played\. The key property that we will exploit is that the policies the human and assistant play are independent given the history, so thatπH\(t\)⊥πA\(t\)∣ℋt\\pi\_\{H\}^\{\(t\)\}~\\bot~\\pi\_\{A\}^\{\(t\)\}\\mid\\mathcal\{H\}\_\{t\}\.

Given aπH\(t−1\)\\pi\_\{H\}^\{\(t\-1\)\}andπR\(t−1\)\\pi\_\{R\}^\{\(t\-1\)\}, what preference should the adversary play? The expected utility that the human and assistant achieve, when the adversary plays stateθ∈Θ\\theta\\in\\Thetais the probability that the agents correctly recoverθ\\theta:

ℙπH\(t\),πA\(t\)​\(θ=πA\(t\)​\(πH\(t\)​\(θ\)\)∣ℋt\)\\displaystyle\\mathbb\{P\}\_\{\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\right\)\\mid\\mathcal\{H\}\_\{t\}\\right\)=∑aH∈𝒜HℙπH\(t\),πA\(t\)​\(θ=πA\(t\)​\(aH\)​and​aH=πH\(t\)​\(θ\)∣ℋt\)\\displaystyle=\\sum\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}\\mathbb\{P\}\_\{\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\text\{ and \}a\_\{H\}=\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\mid\\mathcal\{H\}\_\{t\}\\right\)=∑aH∈𝒜HℙπA\(t\)​\(θ=πA\(t\)​\(aH\)∣ℋt\)​ℙπH\(t\)​\(aH=πH\(t\)​\(θ\)∣ℋt\)\\displaystyle=\\sum\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\mathbb\{P\}\_\{\\pi\_\{H\}^\{\(t\)\}\}\\left\(a\_\{H\}=\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\mid\\mathcal\{H\}\_\{t\}\\right\)=𝔼aH∼πH\(t\)​\(θ\)∣ℋt\[ℙπA\(t\)​\(θ=πA\(t\)​\(aH\)∣ℋt\)\]\.\\displaystyle=\\operatorname\*\{\\mathbb\{E\}\}\_\{a\_\{H\}\\sim\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\mid\\mathcal\{H\}\_\{t\}\}\\bigg\[\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\bigg\]\.We will show that there must always exist a preferenceθ∈Θ\\theta\\in\\Thetasuch that

𝔼aH∼πH\(t\)​\(θ\)∣ℋt\[ℙπA\(t\)​\(θ=πA\(t\)​\(aH\)∣ℋt\)\]≤12\.\\operatorname\*\{\\mathbb\{E\}\}\_\{a\_\{H\}\\sim\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\mid\\mathcal\{H\}\_\{t\}\}\\bigg\[\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\bigg\]\\leq\\frac\{1\}\{2\}\.Order the preferencesθ1,…,θN\\theta\_\{1\},\\dots,\\theta\_\{N\}\. If this is true for any of the firstN−1N\-1preferences, we are done\. Otherwise, it is the case that for alliifrom 1 toN−1N\-1,

𝔼aH∼πH\(t\)​\(θ\)∣ℋt\[ℙπA\(t\)​\(θi=πA\(t\)​\(aH\)∣ℋt\)\]\>12\.\\operatorname\*\{\\mathbb\{E\}\}\_\{a\_\{H\}\\sim\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\mid\\mathcal\{H\}\_\{t\}\}\\bigg\[\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta\_\{i\}=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\bigg\]\>\\frac\{1\}\{2\}\.Therefore, for eachiifrom 1 toN−1N\-1, there must exist someaH,i∈𝒜Ha\_\{H,i\}\\in\\mathcal\{A\}\_\{H\}such that

ℙπA\(t\)​\(θi=πA\(t\)​\(aH,i\)∣ℋt\)\>12\.\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta\_\{i\}=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H,i\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\>\\frac\{1\}\{2\}\.\(1\)For anyiifrom 1 tonn, for any preferenceθ∈Θ\\theta\\in\\Thetawithθ≠θi\\theta\\neq\\theta\_\{i\}:

ℙπA\(t\)​\(θ=πA\(t\)​\(aH,i\)∣ℋt\)\\displaystyle\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H,i\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)=1−ℙπA\(t\)​\(θ≠πA\(t\)​\(aH,i\)∣ℋt\)\\displaystyle=1\-\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta\\neq\\pi\_\{A\}^\{\(t\)\}\(a\_\{H,i\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)≤1−ℙπA\(t\)​\(θi=πA\(t\)​\(aH,i\)∣ℋt\)\\displaystyle\\leq 1\-\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta\_\{i\}=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H,i\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)<1−12=12\.\\displaystyle<1\-\\frac\{1\}\{2\}=\\frac\{1\}\{2\}\.So, for any preferenceθ\\thetathat is notθi\\theta\_\{i\},

ℙπA\(t\)​\(θ=πA\(t\)​\(aH,i\)∣ℋt\)<12\.\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H,i\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)<\\frac\{1\}\{2\}\.\(2\)By Equations \([1](https://arxiv.org/html/2607.08012#A2.E1)\) and \([2](https://arxiv.org/html/2607.08012#A2.E2)\), no twoaH,ia\_\{H,i\}can be equal\. Since this is true forN−1=MHN\-1=M\_\{H\}preferences, and every preference is assigned a unique human action by the above, every human action appears in the set ofaH,i,…,aH,N−1a\_\{H,i\},\\dots,a\_\{H,N\-1\}\. That is, there is a perfect matching between the set of all human actions and the firstN−1N\-1preferences\. When an actionaH,ia\_\{H,i\}is played, it must correspond to some preferenceθi\\theta\_\{i\}with high probability\. Therefore, for the final preferenceθN\\theta\_\{N\}, every action is unlikely to correspond to it, i\.e\. for every actionaH∈𝒜Ha\_\{H\}\\in\\mathcal\{A\}\_\{H\},

ℙπA\(t\)​\(θN=πA\(t\)​\(aH\)∣ℋt\)≤12,\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta\_\{N\}=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\leq\\frac\{1\}\{2\},and so

𝔼aH∼πH\(t\)​\(θ\)∣ℋt\[ℙπA\(t\)​\(θN=πA\(t\)​\(aH\)∣ℋt\)\]≤12\.\\operatorname\*\{\\mathbb\{E\}\}\_\{a\_\{H\}\\sim\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\\mid\\mathcal\{H\}\_\{t\}\}\\bigg\[\\mathbb\{P\}\_\{\\pi\_\{A\}^\{\(t\)\}\}\\left\(\\theta\_\{N\}=\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\\mid\\mathcal\{H\}\_\{t\}\\right\)\\bigg\]\\leq\\frac\{1\}\{2\}\.
So, the adversary can always play a preferenceθ\\thetathat forces the expected utility the agents achieve to be at most12\\frac\{1\}\{2\}\. Whereas in hindsight, the agents could have achieved an average ofN−1N\\frac\{N\-1\}\{N\}per step, resulting in an expected regret of at least:

𝔼\[maxπH,πA∑t=1T𝟙\(θ\(t\)=πA\(πH\(θ\(t\)\)\)−∑t=1T𝟙\(θ\(t\)=πA\(t\)\(πH\(t\)\(θ\(t\)\)\)\)\]≥N−1N⋅T−12⋅T=N−22​N⋅T\.∎\\operatorname\*\{\\mathbb\{E\}\}\\left\[\\max\_\{\\pi\_\{H\},\\pi\_\{A\}\}\\sum\_\{t=1\}^\{T\}\\mathbbm\{1\}\(\\theta^\{\(t\)\}=\\pi\_\{A\}\(\\pi\_\{H\}\(\\theta^\{\(t\)\}\)\)\-\\sum\_\{t=1\}^\{T\}\\mathbbm\{1\}\\left\(\\theta^\{\(t\)\}=\\pi\_\{A\}^\{\(t\)\}\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\\right\)\\right\)\\right\]\\geq\\frac\{N\-1\}\{N\}\\cdot T\-\\frac\{1\}\{2\}\\cdot T=\\frac\{N\-2\}\{2N\}\\cdot T\.\\qed

To extend this result to the case where the number of messages is arbitrary, the adversary can commit beforehand to only using a subset of the states\. It is interesting that even if the learners know which subset of the states the adversary has committed to using, they still cannot achieve sublinear regret\.

###### Theorem B\.2\.

When nature is adaptive, there exist assistance games withN≥3N\\geq 3and1<MH<N1<M\_\{H\}<N, such that any learning algorithm must suffer a regret of at leastMH−12​MH\+2​T\\frac\{M\_\{H\}\-1\}\{2M\_\{H\}\+2\}T\.

###### Proof\.

WhenMHM\_\{H\}may be arbitrary, the adversary may just commit upfront to only sendingMH\+1≤NM\_\{H\}\+1\\leq Nstates, fixed at the start arbitrarily\. SinceMH≥2M\_\{H\}\\geq 2, this means that there areMH\+1≥3M\_\{H\}\+1\\geq 3states, so the lower bound in[Lemma˜B\.1](https://arxiv.org/html/2607.08012#A2.Thmtheorem1)applies directly\. ∎

For the learning algorithms we derive for assistance games to be nontrivial, we then must assume that the adversary is oblivious to the actions of the human and assistant\.

## Appendix CA Lower Bound on Assistance Regret

In this section we prove[Theorem˜4\.3](https://arxiv.org/html/2607.08012#S4.Thmtheorem3), that efficiently achieving an approximation ratio better than1−1/e1\-\\nicefrac\{\{1\}\}\{\{e\}\}is impossible unlessP=NP\\textrm\{P\}=\\textrm\{NP\}\.

First, it will be helpful to consider the offline case, where preferences are drawn from a distribution𝒟\\mathcal\{D\}over preferences, and a human and assistant policy pairπH,πA\\pi\_\{H\},\\pi\_\{A\}must be outputted to maximize the expected reward when preferences are drawn from𝒟\\mathcal\{D\}:

𝔼θ∼𝒟\[r​\(πH​\(θ\),πA​\(πH​\(θ\)\);θ\)\]\.\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\[r\(\\pi\_\{H\}\(\\theta\),\\pi\_\{A\}\(\\pi\_\{H\}\(\\theta\)\);\\theta\)\]\.
We start by showing that achieving an approximation better than1−1/e1\-\\nicefrac\{\{1\}\}\{\{e\}\}in the offline problem is NP\-hard\.

###### Lemma C\.1\(Assistance is NP\-hard\)\.

Computing any \(potentially stochastic\) human\-assistant policy pair that is anα\\alpha\-approximation of the optimal strategy, whereα\>1−1/e\\alpha\>1\-\\nicefrac\{\{1\}\}\{\{e\}\}, in an offline assistance game, even with rewards restricted to be 0 or 1, is NP\-hard\.

###### Proof\.

We will in fact show this offline hardness result for games where the human’s action has no effect on utility\.

Recall that the problem of findingα\\alpha\-approximations to the maxkk\-coverage problem withα\>1−1/e\\alpha\>1\-\\nicefrac\{\{1\}\}\{\{e\}\}is NP\-hard\[Feige,[1998](https://arxiv.org/html/2607.08012#bib.bib16)\]\. Then, we will reduce this to finding anα\\alpha\-approximation of optimal play in an assistance game\. The rewards in this game will be 0 or 1 only\.

We start by recapping thekk\-maximum coverage problem\. Given a valuekkand a collection of setsS=\{S1,…,Sm\}S=\\\{S\_\{1\},\\dots,S\_\{m\}\\\}each with elements in a universe𝒰\\mathcal\{U\}, find a collection ofkksetsSi1,…,SikS\_\{i\_\{1\}\},\\dots,S\_\{i\_\{k\}\}such that\|⋃ℓ=1kSiℓ\|\\left\|\\bigcup\_\{\\ell=1\}^\{k\}S\_\{i\_\{\\ell\}\}\\right\|is maximized\.Feige \[[1998](https://arxiv.org/html/2607.08012#bib.bib16)\]proved that it is NP\-hard to get\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-approximations of the maximumkkcoverage ofSS\.

We now describe a reduction from a maximum coverage problem to solving offline assistance games\. Consider an arbitrarykk\-maximum coverage problem over a collection of setsS=\{S1,…,Sm\}S=\\\{S\_\{1\},\\dots,S\_\{m\}\\\}with elements in𝒰\\mathcal\{U\}\. Create an assistance game where the human’s action set is an arbitrary set of sizeMH=kM\_\{H\}=k, and the space of preferences is𝒰\\mathcal\{U\}\. Make the assistant’s action spaceSS, so that eachSiS\_\{i\}is an assistant action, Set the reward function to

r​\(aH,Si;e\)=\{1ife∈Si,0otherwise\.r\(a\_\{H\},S\_\{i\};e\)=\\begin\{cases\}1&\\text\{if $e\\in S\_\{i\}$,\}\\\\ 0&\\text\{otherwise\.\}\\end\{cases\}The human’s action has no effect on utility and serves only to signal the preference\.

Let the underlying distribution𝒟\\mathcal\{D\}assign an equal probability to each state,1/\|𝒰\|1/\\left\|\\mathcal\{U\}\\right\|\.

We will prove two useful facts about this game\.

1. 1\.Every solution to the max\-MM\-coverage problem induces a solution to this assistance game with the same value\. More precisely, every collection of setsSi1,…,SiMS\_\{i\_\{1\}\},\\dots,S\_\{i\_\{M\}\}, with unionS=⋃j=1MSijS=\\bigcup\_\{j=1\}^\{M\}S\_\{i\_\{j\}\}, induces an human\-assistant policy pairπH,πA\\pi\_\{H\},\\pi\_\{A\}that achieves utility that is at least the value of the sets in the maximum\-MM\-coverage problem:\|S\|/\|𝒰\|\\left\|S\\right\|/\\left\|\\mathcal\{U\}\\right\|\. Indeed, let the human sends messagemjm\_\{j\}when observing a state inSij∖⋃ℓ=1j−1SiℓS\_\{i\_\{j\}\}\\setminus\\bigcup\_\{\\ell=1\}^\{j\-1\}S\_\{i\_\{\\ell\}\}\. The assistant plays setSijS\_\{i\_\{j\}\}upon receiving messagemjm\_\{j\}\. LetS=⋃j=1MSiS=\\bigcup\_\{j=1\}^\{M\}S\_\{i\}\. Whenever a preference inSSappears, the agents get a reward of 1, and so the expected reward of this human\-assistant policy pair is\|S\|/\|𝒰\|\\left\|S\\right\|/\\left\|\\mathcal\{U\}\\right\|, precisely the value of the sets in the maximum\-MM\-coverage problem\.
2. 2\.Every solution with a deterministic assistant policy to this assistance game induces a solution to the max\-MM\-coverage problem with at least the same value\. More precisely, given a deterministic assistant policyπA\\pi\_\{A\}, we will construct a collection of setsSi1,…,SiMS\_\{i\_\{1\}\},\\dots,S\_\{i\_\{M\}\}, with unionS=⋃j=1MSijS=\\bigcup\_\{j=1\}^\{M\}S\_\{i\_\{j\}\}, so that for any human policyπH\\pi\_\{H\}, the utilityπH,πA\\pi\_\{H\},\\pi\_\{A\}achieves utility is at most the value of the sets in the maximum\-MM\-coverage problem:\|S\|/\|𝒰\|\\left\|S\\right\|/\\left\|\\mathcal\{U\}\\right\|\. πA\\pi\_\{A\}maps each message to an actionSiS\_\{i\}\. There areMHM\_\{H\}possible messages, so simply take theMHM\_\{H\}actions,Si1,…,SiMS\_\{i\_\{1\}\},\\dots,S\_\{i\_\{M\}\}, that the assistant chooses to play as the solution to the maximum coverage problem\. LetS=⋃j=1MSijS=\\bigcup\_\{j=1\}^\{M\}S\_\{i\_\{j\}\}\. The valueπA\\pi\_\{A\}achieves with any human policyπH\\pi\_\{H\}is at most the probability that elements inSSappear:\|S\|/\|𝒰\|\\left\|S\\right\|/\\left\|\\mathcal\{U\}\\right\|\.

These reductions back and forth imply that the optimal values of both problems are equal\.

In general assistance games, given a human policyπH\\pi\_\{H\}that is not necessarily deterministic, there exists a deterministic best\-response assistant policyπA∗\\pi\_\{A\}^\{\*\}that can be found by an efficient algorithm\. Indeed, given a human actionaH∈𝒜Ha\_\{H\}\\in\\mathcal\{A\}\_\{H\}the value of playing actionaA∈𝒜Aa\_\{A\}\\in\\mathcal\{A\}\_\{A\}for the assistant is

𝔼θ∼𝒟\[r​\(aH,aA,θ\)∣πH​\(θ\)=aH\]\\displaystyle\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\[r\(a\_\{H\},a\_\{A\},\\theta\)\\mid\\pi\_\{H\}\(\\theta\)=a\_\{H\}\]=∑θ∈Θℙ​\(θ∣πH​\(θ\)=aH\)​r​\(aH,aA,θ\)\\displaystyle=\\sum\_\{\\theta\\in\\Theta\}\\mathbb\{P\}\(\\theta\\mid\\pi\_\{H\}\(\\theta\)=a\_\{H\}\)r\(a\_\{H\},a\_\{A\},\\theta\)=∑θ∈Θℙ​\(θ\)​ℙ​\(πH​\(θ\)=aH\)∑θ′∈Θℙ​\(θ′\)​ℙ​\(πH​\(θ′\)=m\)​r​\(aH,aA,θ\),\\displaystyle=\\sum\_\{\\theta\\in\\Theta\}\\frac\{\\mathbb\{P\}\(\\theta\)\\mathbb\{P\}\(\\pi\_\{H\}\(\\theta\)=a\_\{H\}\)\}\{\\sum\_\{\\theta^\{\\prime\}\\in\\Theta\}\\mathbb\{P\}\(\\theta^\{\\prime\}\)\\mathbb\{P\}\(\\pi\_\{H\}\(\\theta^\{\\prime\}\)=m\)\}r\(a\_\{H\},a\_\{A\},\\theta\),which can be computed in polynomial time in the number of actions and states\. The reward any response achieves is linear, and the optimal deterministically plays the action with largest expected reward given the human action observed\.

Using these two facts, we can reduce the problem of finding anα\\alpha\-approximation of thekk\-maximum coverage problem to finding anα\\alpha\-approximation of the optimal human\-assistant policy pair in this assistance game\. Suppose\(πH,πA\)\(\\pi\_\{H\},\\pi\_\{A\}\)are a human\-assistant policy pair that achieve anα\\alpha\-approximation of optimal play in this assistance game\.\(πH,πR\)\(\\pi\_\{H\},\\pi\_\{R\}\)may not necessarily be deterministic\. But, by the above, we can construct in polynomial time a deterministic assistant policyπA′\\pi\_\{A\}^\{\\prime\}that achieves at least the same reward when paired withπH\\pi\_\{H\}\.

Applying fact 2 onπA′\\pi\_\{A\}^\{\\prime\}this means that we have found a collection of setsSi1,…,SikS\_\{i\_\{1\}\},\\dots,S\_\{i\_\{k\}\}that achieve at leastα\\alphatimes the max reward of the assistance game\. So we have shown that the optimal reward in this game is equal to the optimal reward in the maximum\-kk\-coverage problem, and we are done\! ∎

With this tool in hand, we can show that, unlessRP=NP\\textrm\{RP\}=\\textrm\{NP\}, efficient learning algorithms for assistance games that achieve approximate utility better than1−1/e1\-\\nicefrac\{\{1\}\}\{\{e\}\}cannot exist\.

See[4\.3](https://arxiv.org/html/2607.08012#S4.Thmtheorem3)

###### Proof of[Theorem˜4\.3](https://arxiv.org/html/2607.08012#S4.Thmtheorem3)\.

Suppose for the sake of contradiction thatRT∈𝒪​\(T1−ϵ\)R\_\{T\}\\in\\mathcal\{O\}\\left\(T^\{1\-\\epsilon\}\\right\)for someϵ\>0\\epsilon\>0\.

We can write for some constantsc1,c2,a,b,c∈ℝc\_\{1\},c\_\{2\},a,b,c\\in\\mathbb\{R\}, thatRT​\(N,M\)≤c1​Na​MHb​MAc​T1−ϵ\+c2R\_\{T\}\(N,M\)\\leq c\_\{1\}N^\{a\}M\_\{H\}^\{b\}M\_\{A\}^\{c\}T^\{1\-\\epsilon\}\+c\_\{2\}\. This means that the average regret per time step is at most

c1​Na​MHb​MAcTϵ\+c2T\.\\frac\{c\_\{1\}N^\{a\}M\_\{H\}^\{b\}M\_\{A\}^\{c\}\}\{T^\{\\epsilon\}\}\+\\frac\{c\_\{2\}\}\{T\}\.
The rest of the proof will follow the lead ofKapralov et al\. \[[2013](https://arxiv.org/html/2607.08012#bib.bib33)\]\. Given a valuek∈ℕk\\in\\mathbb\{N\}and a collection of setsS=\{S1,…,Sm\}S=\\\{S\_\{1\},\\dots,S\_\{m\}\\\}each with elements in a universe𝒰\\mathcal\{U\},Feige \[[1998](https://arxiv.org/html/2607.08012#bib.bib16)\]proved that, for anyδ\>0\\delta\>0, it is NP\-hard to distinguish between the following two cases:

1. 1\.Yes case: Some choice ofkksets covers𝒰\\mathcal\{U\}\.
2. 2\.No case: No choice ofkksets covers a1−1/e\+δ1\-\\nicefrac\{\{1\}\}\{\{e\}\}\+\\deltaproportion of the elements in𝒰\\mathcal\{U\}\.

Therefore, if there is a polynomial\-time algorithm that outputs yes with constant probability when in the yes case, and outputs no always when in the no case, it must be thatRP=NP\\text\{RP\}=\\text\{NP\}\.

Suppose there exists an efficient no\-α\\alpha\-approximate regret assistance game learning algorithm\. We will show that the problem above forδ=α−\(1−1/e\)2\\delta=\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{2\}can be solved with a constant probability of success in the yes case, and always in the no case\. This would proveRP=NP\\text\{RP\}=\\text\{NP\}\.

Given an instance of the set\-cover problem, run the algorithm on the corresponding assistance game derived in[Lemma˜C\.1](https://arxiv.org/html/2607.08012#A3.Thmtheorem1)\. As we show in[Lemma˜C\.1](https://arxiv.org/html/2607.08012#A3.Thmtheorem1), the optimal value in this game is equal to that of the set\-cover problem\.

Run the no\-α\\alpha\-approximate regret learning algorithm for

T=max⁡\(c2,\(\(α−\(1\+1/e\)4\)​c1​Na​MHb​MAc\)1/ϵ\)∈poly​\(N,M\)T=\\max\\left\(c\_\{2\},~\\left\(\\left\(\\frac\{\\alpha\-\(1\+\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}\\right\)c\_\{1\}N^\{a\}M\_\{H\}^\{b\}M\_\{A\}^\{c\}\\right\)^\{\\nicefrac\{\{1\}\}\{\{\\epsilon\}\}\}\\right\)\\in\\text\{poly\}\(N,M\)steps, and the average regret per iteration becomes at mostα−\(1−1/e\)4\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}\.

First, notice that we may as well pretend that the human and assistant output their full policy at every stepπH\(t\)\\pi\_\{H\}^\{\(t\)\}andπA\(t\)\\pi\_\{A\}^\{\(t\)\}at every step, not justπH\(t\)​\(θ\(t\)\)\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)andπA\(t\)​\(πH\(t\)​\(θ\(t\)\)\)\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\)\. This is because at every step of the learning algorithm, we can createMHM\_\{H\}andMAM\_\{A\}copies and ask for the distribution over actions on every counterfactual input\.

The reduction will be as follows\. Run the algorithm onTTi\.i\.d drawsθ\(1\),…,θ\(T\)∼𝒟T\\theta^\{\(1\)\},\\dots,\\theta^\{\(T\)\}\\sim\\mathcal\{D\}^\{T\}, induce a sequence of human\-assistant policy pairs\(πH\(1\),πA\(1\)\),…,\(πH\(T\),πA\(T\)\)\(\\pi\_\{H\}^\{\(1\)\},\\pi\_\{A\}^\{\(1\)\}\),\\dots,\(\\pi\_\{H\}^\{\(T\)\},\\pi\_\{A\}^\{\(T\)\}\), compute the expected reward of each human\-assistant policy pair averaged over𝒟\\mathcal\{D\}\(which we can do in at most𝒪​\(N\)\\mathcal\{O\}\\left\(N\\right\)time each\), and output yes if some pairπH\(t\),πA\(t\)\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}exists with expected reward at leastα−3​\(α−\(1−1/e\)\)8\\alpha\-\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\}, and no otherwise\.

When we are in the no case, no solution will have expected reward in the assistance game that is at leastα−3​\(α−\(1−1/e\)\)8\\alpha\-\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\}, so we will always output no\.

Suppose we are in the yes case, so that the optimal utility is 1\. Because we run for long enough that average regret isα−\(1−1/e\)4\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}, we can say

𝔼θ1:T∼𝒟T\[1T​∑t=1Tr​\(πH\(t\)​\(θ\(t\)\),πA\(t\)​\(πH\(t\)​\(θ\(t\)\)\);θ\(t\)\)\]≥α−α−\(1−1/e\)4\.\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\);~\\theta^\{\(t\)\}\\right\)\\right\]\\geq\\alpha\-\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}\.\(3\)To move forward, we will need to remove the dependence onθ\(t\)\\theta^\{\(t\)\}in the expected reward\. Notice thatθ\(t\)⊥\(πH\(t\),πA\(t\)\)\\theta^\{\(t\)\}\\bot\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\), asθ\(t\)\\theta^\{\(t\)\}is sampled from𝒟\\mathcal\{D\}, andπH\(t\),πA\(t\)\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}depends only onθ\(1\),…,θ\(t−1\)\\theta^\{\(1\)\},\\dots,\\theta^\{\(t\-1\)\}, which themselves are independent ofθ\(t\)\\theta^\{\(t\)\}\. Therefore, for anytt, it must be that

𝔼θ1:T∼𝒟T\[r​\(πH\(t\)​\(θ\(t\)\),πA\(t\)​\(πH\(t\)​\(θ\(t\)\)\);θ\(t\)\)\]\\displaystyle\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\);~\\theta^\{\(t\)\}\\right\)\\right\]=𝔼θ1:\(t−1\)∼𝒟\(t−1\)𝔼θ\(t\)∼𝒟\[r​\(πH\(t\)​\(θ\(t\)\),πA\(t\)​\(πH\(t\)​\(θ\(t\)\)\);θ\(t\)\)∣θ\(1\),…,θ\(t−1\)\]\\displaystyle=\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:\(t\-1\)\}\\sim\\mathcal\{D\}^\{\(t\-1\)\}\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{\(t\)\}\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\);~\\theta^\{\(t\)\}\\right\)\\mid\\theta^\{\(1\)\},\\dots,\\theta^\{\(t\-1\)\}\\right\]=𝔼θ1:\(t−1\)∼𝒟\(t−1\)𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]\.\\displaystyle=\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:\(t\-1\)\}\\sim\\mathcal\{D\}^\{\(t\-1\)\}\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\.\(4\)And so by the linearity of expectation,

𝔼θ1:T∼𝒟T\[1T​∑t=1Tr​\(πH\(t\)​\(θ\(t\)\),πA\(t\)​\(πH\(t\)​\(θ\(t\)\)\);θ\(t\)\)\]\\displaystyle\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\);~\\theta^\{\(t\)\}\\right\)\\right\]=1T​∑t=1T𝔼θ1:T∼𝒟T\[r​\(πH\(t\)​\(θ\(t\)\),πA\(t\)​\(πH\(t\)​\(θ\(t\)\)\);θ\(t\)\)\]\\displaystyle=\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\);~\\theta^\{\(t\)\}\\right\)\\right\]=1T​∑t=1T𝔼θ1:\(t−1\)∼𝒟\(t−1\)𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]\\displaystyle=\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:\(t\-1\)\}\\sim\\mathcal\{D\}^\{\(t\-1\)\}\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\(By[Equation˜4](https://arxiv.org/html/2607.08012#A3.E4)\)\\displaystyle\(\\text\{By \\lx@cref\{creftypecap~refnum\}\{eq:lower\-bound\-sub\-expected\}\}\)=1T​∑t=1T𝔼θ1:T∼𝒟T𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]\\displaystyle=\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]=𝔼θ1:T∼𝒟T\[1T​∑t=1T𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]\]\\displaystyle=\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\\right\]Plugging this into \([3](https://arxiv.org/html/2607.08012#A3.E3)\),

𝔼θ1:T∼𝒟T\[1T​∑t=1T𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]\]≥α−α−\(1−1/e\)4\.\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta^\{1:T\}\\sim\\mathcal\{D\}^\{T\}\}\\left\[\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\\right\]\\geq\\alpha\-\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}\.LetX¯=1T​∑t=1T𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]\\bar\{X\}=\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\. Since rewards lie in\[0,1\]\[0,1\], the random variable1−X¯1\-\\bar\{X\}is non\-negative, and the displayed inequality above bounds𝔼\[1−X¯\]≤1−α\+α−\(1−1/e\)4\\operatorname\*\{\\mathbb\{E\}\}\[1\-\\bar\{X\}\]\\leq 1\-\\alpha\+\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}\. By Markov’s inequality applied to1−X¯1\-\\bar\{X\},

Pr⁡\[X¯<α−3​\(α−\(1−1/e\)\)8\]=Pr⁡\[1−X¯\>1−α\+3​\(α−\(1−1/e\)\)8\]≤1−α\+α−\(1−1/e\)41−α\+3​\(α−\(1−1/e\)\)8,\\Pr\\\!\\left\[\\bar\{X\}\\,<\\,\\alpha\-\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\}\\right\]\\;=\\;\\Pr\\\!\\left\[1\-\\bar\{X\}\\,\>\\,1\-\\alpha\+\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\}\\right\]\\;\\leq\\;\\frac\{1\-\\alpha\+\\frac\{\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\}\{4\}\}\{1\-\\alpha\+\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\}\},and the right\-hand side is a constant strictly less than11for any fixedα\>1−1/e\\alpha\>1\-\\nicefrac\{\{1\}\}\{\{e\}\}\. Therefore, with constant probability,

1T​∑t=1T𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]≥α−3​\(α−\(1−1/e\)\)8\.\\frac\{1\}\{T\}\\sum\_\{t=1\}^\{T\}\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\\geq\\alpha\-\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\}\.Because it is an average, we can say in this case that there must exist somettsuch that

𝔼θ∼𝒟\[r​\(πH\(t\)​\(θ\),πA\(t\)​\(πH\(t\)​\(θ\)\);θ\)\]≥α−3​\(α−\(1−1/e\)\)8,\\operatorname\*\{\\mathbb\{E\}\}\_\{\\theta\\sim\\mathcal\{D\}\}\\left\[r\\left\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\),~\\pi\_\{A\}^\{\(t\)\}\(\\pi\_\{H\}^\{\(t\)\}\(\\theta\)\);~\\theta\\right\)\\right\]\\geq\\alpha\-\\frac\{3\(\\alpha\-\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\)\}\{8\},and our reduction will find it\.

Thus, we can efficiently determine whether we are in the yes case with constant probability, and we are done\! ∎

## Appendix DMissing proofs

### D\.1Proof of[Lemma˜D\.1](https://arxiv.org/html/2607.08012#A4.Thmtheorem1)

###### Lemma D\.1\(Assistance Matroid is a Partition Matroid, restated\)\.

For any assistance gameGG, the corresponding assistance matroidℳG=\(𝒰G,ℐG\)\\mathcal\{M\}\_\{G\}=\(\\mathcal\{U\}\_\{G\},\\mathcal\{I\}\_\{G\}\)defined in[Definition˜5\.2](https://arxiv.org/html/2607.08012#S5.Thmtheorem2)is a partition matroid with rankMHM\_\{H\}\([Definition˜A\.3](https://arxiv.org/html/2607.08012#A1.Thmtheorem3)\)\.

###### Proof\.

The maximum size ofS∈ℐGS\\in\\mathcal\{I\}\_\{G\}isMHM\_\{H\}because there can be at most one action pair for each human action\. So the rank ofℳG\\mathcal\{M\}\_\{G\}isMHM\_\{H\}\. To see why this is a partition matroid, consider partitioning the ground set𝒰G\\mathcal\{U\}\_\{G\}into disjoint sets𝒰aH=\{aH\}×𝒜A\\mathcal\{U\}\_\{a\_\{H\}\}=\\\{a\_\{H\}\\\}\\times\\mathcal\{A\}\_\{A\}with capacitiesdaH=1d\_\{a\_\{H\}\}=1foraH∈𝒜Ha\_\{H\}\\in\\mathcal\{A\}\_\{H\}\. Since no two human actions are in the same independent set, we have\|ℐG∩𝒰aH\|=daH=1\|\\mathcal\{I\}\_\{G\}\\cap\\mathcal\{U\}\_\{a\_\{H\}\}\|=d\_\{a\_\{H\}\}=1\. This completes the proof\. ∎

### D\.2Proof of[Proposition˜5\.4](https://arxiv.org/html/2607.08012#S5.Thmtheorem4)

For every independent setI∈ℐGI\\in\\mathcal\{I\}\_\{G\}, let𝒜HI=\{aH∈𝒜H∣∃aA∈𝒜A:\(aH,aA\)∈I\}\\mathcal\{A\}\_\{H\}^\{I\}=\\\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\\mid\\exists a\_\{A\}\\in\\mathcal\{A\}\_\{A\}:\(a\_\{H\},a\_\{A\}\)\\in I\\\}be the set of human actions paired with an assistant action inII\. IfI=∅I=\\emptyset, thenVθ​\(I\)=0V\_\{\\theta\}\(I\)=0, and any policy pair achieves reward at least 0 by definition\.

Otherwise, we can define the associated assistant policy as playing, in response to any human actionaH∈𝒜HIa\_\{H\}\\in\\mathcal\{A\}\_\{H\}^\{I\}the assistant action paired withaHa\_\{H\}inII, and in response to any human actionaH∉𝒜HIa\_\{H\}\\notin\\mathcal\{A\}\_\{H\}^\{I\}an arbitrary assistant actionaA¯∈𝒜A\\overline\{a\_\{A\}\}\\in\\mathcal\{A\}\_\{A\}:

πAI​\(aH\)=\{aAifaH∈𝒜HIand\(aH,aA\)∈I,aA¯ifaH∉𝒜HI\.\\pi\_\{A\}^\{I\}\(a\_\{H\}\)=\\begin\{cases\}a\_\{A\}&\\text\{if $a\_\{H\}\\in\\mathcal\{A\}\_\{H\}^\{I\}$ and $\(a\_\{H\},a\_\{A\}\)\\in I$\},\\\\ \\overline\{a\_\{A\}\}&\\text\{if $a\_\{H\}\\notin\\mathcal\{A\}\_\{H\}^\{I\}$\}\.\\end\{cases\}This is well\-defined: because the setIIis independent, every human action is paired with at most one assistant action\.

Defining the associated human policyπHI:Θ→𝒜H\\pi\_\{H\}^\{I\}:\\Theta\\to\\mathcal\{A\}\_\{H\}as being the one that plays the optimal response toπAI\\pi\_\{A\}^\{I\}with actions in𝒜HI\\mathcal\{A\}\_\{H\}^\{I\},

πHI​\(θ\)=arg⁡maxaH∈𝒜HI⁡r​\(aH,aA;θ\),\\pi\_\{H\}^\{I\}\(\\theta\)=\\operatorname\*\{\\arg\\\!\\max\}\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}^\{I\}\}~r\(a\_\{H\},a\_\{A\};\\theta\),the reward the policiesπHI\\pi\_\{H\}^\{I\}andπAI\\pi\_\{A\}^\{I\}achieve when paired together on preferenceθ\\thetais exactly the valueVθ​\(I\)V\_\{\\theta\}\(I\):

r​\(πHI​\(θ\),πAI​\(πHI​\(θ\)\);θ\)=maxaH∈𝒜HI⁡r​\(aH,πAI​\(aH\);θ\)=max\(aH,aA\)∈I⁡r​\(aH,aA;θ\)=Vθ​\(I\)\.\\displaystyle r\(\\pi\_\{H\}^\{I\}\(\\theta\),\\pi\_\{A\}^\{I\}\(\\pi\_\{H\}^\{I\}\(\\theta\)\);\\theta\)=\\max\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}^\{I\}\}r\(a\_\{H\},\\pi\_\{A\}^\{I\}\(a\_\{H\}\);\\theta\)=\\max\_\{\(a\_\{H\},a\_\{A\}\)\\in I\}r\(a\_\{H\},a\_\{A\};\\theta\)=V\_\{\\theta\}\(I\)\.
This proves the first condition\. For the second, given any assistant policyπA∈ΠA\\pi\_\{A\}\\in\\Pi\_\{A\}define the set

IπA=\{\(aH,πA​\(aH\)\)∈𝒰G:aH∈𝒜H\}\.I\_\{\\pi\_\{A\}\}=\\\{\(a\_\{H\},\\pi\_\{A\}\(a\_\{H\}\)\)\\in\\mathcal\{U\}\_\{G\}:a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\\\}\.Because everyaHa\_\{H\}appears in one pair inIπAI\_\{\\pi\_\{A\}\},IπAI\_\{\\pi\_\{A\}\}is an independent set inℳG\\mathcal\{M\}\_\{G\}\. For every preferenceθ∈Θ\\theta\\in\\Thetaand every human policyπH:Θ→𝒜H\\pi\_\{H\}:\\Theta\\to\\mathcal\{A\}\_\{H\}, it follows that

r​\(πH​\(θ\),πA​\(πH​\(θ\)\);θ\)≤maxaH∈𝒜H⁡r​\(aH,πA​\(aH\);θ\)=maxaH,aA∈IπA⁡r​\(aH,aA;θ\)=Vθ​\(IπA\)\.\\displaystyle r\(\\pi\_\{H\}\(\\theta\),\\pi\_\{A\}\(\\pi\_\{H\}\(\\theta\)\);\\theta\)\\leq\\max\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}r\(a\_\{H\},\\pi\_\{A\}\(a\_\{H\}\);\\theta\)=\\max\_\{a\_\{H\},a\_\{A\}\\in I\_\{\\pi\_\{A\}\}\}r\(a\_\{H\},a\_\{A\};\\theta\)=V\_\{\\theta\}\(I\_\{\\pi\_\{A\}\}\)\.\\quad∎

### D\.3Structural properties of the value of assistance function

###### Lemma D\.2\(restated\)\.

The value of assistance functionVθV\_\{\\theta\}is a weighted threshold potential \([Definition˜A\.2](https://arxiv.org/html/2607.08012#A1.Thmtheorem2)\)\.

###### Proof\.

Fix aθ∈Θ\\theta\\in\\Theta\. We will show thatVθV\_\{\\theta\}is a weighted threshold potential\. Sort the valuesr​\(aH,aA;θ\)r\(a\_\{H\},a\_\{A\};\\theta\)from largest to smallest,α1,…,αMH​MA\\alpha\_\{1\},\\dots,\\alpha\_\{M\_\{H\}M\_\{A\}\}, whereαi\\alpha\_\{i\}is theiith largest reward a human\-assistant action pair can achieve, and let\(aH\(1\),aA\(1\)\),…,\(aH\(MH​MA\),aA\(MH​MA\)\)\\left\(a\_\{H\}^\{\(1\)\},a\_\{A\}^\{\(1\)\}\\right\),\\dots,\\left\(a\_\{H\}^\{\(M\_\{H\}M\_\{A\}\)\},a\_\{A\}^\{\(M\_\{H\}M\_\{A\}\)\}\\right\)be the corresponding ordering of human\-assistant action pairs from highest to lowest\. SetαMH​MA\+1=0\\alpha\_\{M\_\{H\}M\_\{A\}\+1\}=0\.

The key trick is to rewrite the difference between the max over any non\-emptySSand the overall minimum over𝒜H×𝒜A\\mathcal\{A\}\_\{H\}\\times\\mathcal\{A\}\_\{A\}as a telescoping sum:

max\(aH,aA\)∈Sr\(aH,aA;θ\)=∑k=1MH​MA\(αk−αk\+1\)⋅𝟙\(∃i≤k:\(aH\(i\),aA\(i\)\)∈S\)\.\\max\_\{\(a\_\{H\},a\_\{A\}\)\\in S\}r\(a\_\{H\},a\_\{A\};\\theta\)=\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\(\\alpha\_\{k\}\-\\alpha\_\{k\+1\}\)\\cdot\\mathds\{1\}\\left\(\\exists i\\leq k:\\left\(a\_\{H\}^\{\(i\)\},a\_\{A\}^\{\(i\)\}\\right\)\\in S\\right\)\.The indicator function𝟙\(∃i≤k:\(aH\(i\),aA\(i\)\)∈S\)\\mathds\{1\}\\left\(\\exists i\\leq k:\\left\(a\_\{H\}^\{\(i\)\},a\_\{A\}^\{\(i\)\}\\right\)\\in S\\right\)is a budget\-additive function

𝟙\(∃i≤k:\(aH\(i\),aA\(i\)\)∈S\)=min\{1,∑i∈Swik\},\\mathds\{1\}\\left\(\\exists i\\leq k:\\left\(a\_\{H\}^\{\(i\)\},a\_\{A\}^\{\(i\)\}\\right\)\\in S\\right\)=\\min\\left\\\{1,~\\sum\_\{i\\in S\}w\_\{i\}^\{k\}\\right\\\},wherewik=𝟙​\(i≤k\)w\_\{i\}^\{k\}=\\mathds\{1\}\(i\\leq k\)\. So, defining the modular functiongk​\(S\)=∑i∈Swikg\_\{k\}\(S\)=\\sum\_\{i\\in S\}w\_\{i\}^\{k\}, we can write

max\(aH,aA\)∈S⁡r​\(aH,aA;θ\)=∑k=1MH​MA\(αk−αk\+1\)⋅min⁡\{1,gk​\(S\)\}\.\\max\_\{\(a\_\{H\},a\_\{A\}\)\\in S\}r\(a\_\{H\},a\_\{A\};\\theta\)=\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\(\\alpha\_\{k\}\-\\alpha\_\{k\+1\}\)\\cdot\\min\\left\\\{1,~g\_\{k\}\(S\)\\right\\\}\.
Because the list ofαi\\alpha\_\{i\}is ordered, it follows thatαk≥αk\+1\\alpha\_\{k\}\\geq\\alpha\_\{k\+1\}, and so all the coefficients are non\-negative\. By definition,max\(aH,aA\)∈S⁡r​\(aH,aA;θ\)=Vθ​\(S\)\\max\_\{\(a\_\{H\},a\_\{A\}\)\\in S\}r\(a\_\{H\},a\_\{A\};\\theta\)=V\_\{\\theta\}\(S\)\. So, all in all, whenSSis non\-empty, we can write the value of assistance function as a non\-negative linear combination of weighted threshold potentials

Vθ​\(S\)=∑k=1MH​MA\(αk−αk\+1\)⋅min⁡\{1,gk​\(S\)\}\.\\displaystyle V\_\{\\theta\}\(S\)=\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\(\\alpha\_\{k\}\-\\alpha\_\{k\+1\}\)\\cdot\\min\\left\\\{1,~g\_\{k\}\(S\)\\right\\\}\.\(5\)WhenS=∅S=\\emptyset, both sides are 0, so the equality always holds\. ∎

For the value of assistance functionVθV\_\{\\theta\}written in weighted threshold potential form \([Equation˜5](https://arxiv.org/html/2607.08012#A4.E5)\), the concave relaxation over the matroid polytope𝒴=conv​\{𝟙S:S∈ℐG\}\\mathcal\{Y\}=\\mathrm\{conv\}\\\{\\mathds\{1\}\_\{S\}:S\\in\\mathcal\{I\}\_\{G\}\\\}is

V~θ​\(𝐲\)=∑k=1MH​MA\(αk−αk\+1\)⋅min⁡\{1,∑i=1ky\(aH\(i\),aA\(i\)\)\},\\displaystyle\\tilde\{V\}\_\{\\theta\}\(\\mathbf\{y\}\)=\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\(\\alpha\_\{k\}\-\\alpha\_\{k\+1\}\)\\cdot\\min\\left\\\{1,~\\sum\_\{i=1\}^\{k\}y\_\{\(a\_\{H\}^\{\(i\)\},a\_\{A\}^\{\(i\)\}\)\}\\right\\\},where𝐲∈𝒴⊆\[0,1\]MH​MA\\mathbf\{y\}\\in\\mathcal\{Y\}\\subseteq\[0,1\]^\{M\_\{H\}M\_\{A\}\}\.

###### Lemma D\.3\(restated\)\.

For any preferenceθ∈Θ\\theta\\in\\Theta, the concave relaxationV~θ\\tilde\{V\}\_\{\\theta\}of the value of assistance function is11\-Lipschitz with respect to theℓ1\\ell\_\{1\}norm over𝒴=\[0,1\]MH​MA\\mathcal\{Y\}=\[0,1\]^\{M\_\{H\}M\_\{A\}\}\.

###### Proof\.

Considerθ\\thetaand the corresponding concave relaxationV~θ\\tilde\{V\}\_\{\\theta\}defined in[Definition˜A\.4](https://arxiv.org/html/2607.08012#A1.Thmtheorem4)\. We can writeV~θ​\(𝐲\)=∑k=1MH​MA\|ck\|​min⁡\{1,𝐰k⊤​𝐲\}\\tilde\{V\}\_\{\\theta\}\(\\mathbf\{y\}\)=\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\|c\_\{k\}\|\\min\\\{1,\\mathbf\{w\}\_\{k\}^\{\\top\}\\mathbf\{y\}\\\}where\|ck\|=\|αk−αk\+1\|\|c\_\{k\}\|=\|\\alpha\_\{k\}\-\\alpha\_\{k\+1\}\|and𝐰k∈\{0,1\}MH​MA\\mathbf\{w\}\_\{k\}\\in\\\{0,1\\\}^\{M\_\{H\}M\_\{A\}\}are coefficients and weight vectors derived in the proof of[Lemma˜D\.2](https://arxiv.org/html/2607.08012#A4.Thmtheorem2)where we express the value of assistance functions in the form of weighted threshold potentials\. For any𝐲,𝐲′∈𝒴\\mathbf\{y\},\\mathbf\{y^\{\\prime\}\}\\in\\mathcal\{Y\}:

\|V~θ​\(𝐲\)−V~θ​\(𝐲′\)\|\\displaystyle\|\\tilde\{V\}\_\{\\theta\}\(\\mathbf\{y\}\)\-\\tilde\{V\}\_\{\\theta\}\(\\mathbf\{y^\{\\prime\}\}\)\|≤∑k=1MH​MA\|ck\|​\|min⁡\{1,𝐰k⊤​𝐲\}−min⁡\{1,𝐰k⊤​𝐲′\}\|\\displaystyle\\leq\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\|c\_\{k\}\|\\left\|\\min\\\{1,\\mathbf\{w\}\_\{k\}^\{\\top\}\\mathbf\{y\}\\\}\-\\min\\\{1,\\mathbf\{w\}\_\{k\}^\{\\top\}\\mathbf\{y^\{\\prime\}\}\\\}\\right\|≤∑k=1MH​MA\|ck\|​\|𝐰k⊤​\(𝐲−𝐲′\)\|\\displaystyle\\leq\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\|c\_\{k\}\|\\left\|\\mathbf\{w\}\_\{k\}^\{\\top\}\(\\mathbf\{y\}\-\\mathbf\{y^\{\\prime\}\}\)\\right\|≤∑k=1MH​MA\|ck\|⋅‖𝐰k‖∞⋅‖𝐲−𝐲′‖1\\displaystyle\\leq\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\|c\_\{k\}\|\\cdot\\\|\\mathbf\{w\}\_\{k\}\\\|\_\{\\infty\}\\cdot\\\|\\mathbf\{y\}\-\\mathbf\{y^\{\\prime\}\}\\\|\_\{1\}≤\(∑k=1MH​MA\|ck\|\)​‖𝐲−𝐲′‖1\.\\displaystyle\\leq\\left\(\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\|c\_\{k\}\|\\right\)\\\|\\mathbf\{y\}\-\\mathbf\{y^\{\\prime\}\}\\\|\_\{1\}\.This shows that the functionV~θ\\tilde\{V\}\_\{\\theta\}is Lipschitz with Lipschitz constant:

∑k=1MH​MA\|ck\|=∑k=1MH​MA\(αk−αk\+1\)=α1−αMH​MA\+1=α1≤1\.\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\|c\_\{k\}\|=\\sum\_\{k=1\}^\{M\_\{H\}M\_\{A\}\}\(\\alpha\_\{k\}\-\\alpha\_\{k\+1\}\)=\\alpha\_\{1\}\-\\alpha\_\{M\_\{H\}M\_\{A\}\+1\}=\\alpha\_\{1\}\\leq 1\.Where the last inequality holds because rewards are bounded in\[0,1\]\[0,1\]\. ∎

### D\.4Proof of[Proposition˜5\.1](https://arxiv.org/html/2607.08012#S5.Thmtheorem1)

By[Proposition˜5\.4](https://arxiv.org/html/2607.08012#S5.Thmtheorem4), the centralized assistance game reduces to online maximization of value of assistance functions over the assistance matroidℳG\\mathcal\{M\}\_\{G\}\. The assistance matroid has ground set size\|𝒰G\|=MH​MA\|\\mathcal\{U\}\_\{G\}\|=M\_\{H\}M\_\{A\}and rankMHM\_\{H\}\([Lemma˜D\.1](https://arxiv.org/html/2607.08012#A4.Thmtheorem1)\)\. By[Lemma˜D\.2](https://arxiv.org/html/2607.08012#A4.Thmtheorem2)and[Lemma˜D\.3](https://arxiv.org/html/2607.08012#A4.Thmtheorem3), the value of assistance functions are weighted threshold potentials and their concave relaxations are11\-Lipschitz\. Applying the RAOCO algorithm ofSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]with these parameters yields apoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\)time algorithm with expected\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-approximate regret𝒪​\(MH​T​log⁡MA\)\\mathcal\{O\}\\left\(M\_\{H\}\\sqrt\{T\\log M\_\{A\}\}\\right\)\. This is a direct result of the regret analysis done inSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]which is restated as[Proposition˜E\.2](https://arxiv.org/html/2607.08012#A5.Thmtheorem2)in the appendix\. ∎

### D\.5Proof of[Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)

Let\(π¯H\(t\),π¯A\(t\)\)\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\overline\{\\pi\}\_\{A\}^\{\(t\)\}\\right\)be the policy pair output byAlgC\\mathrm\{Alg\}\_\{C\}at roundtt\. By our construction ofAlgH\\mathrm\{Alg\}\_\{H\}, the human policy played in roundttisπ¯H\(t\)\\overline\{\\pi\}\_\{H\}^\{\(t\)\}\. LetπA\(t\)\\pi\_\{A\}^\{\(t\)\}denote the assistant policy played byAlgA\\mathrm\{Alg\}\_\{A\}in roundtt\. The assistance regret of the decentralized pair is

RTα=α​maxπH,πA​∑t=1Trt​\(πH,πA\)−∑t=1Trt​\(π¯H\(t\),πA\(t\)\)\.R^\{\\alpha\}\_\{T\}=\\alpha\\max\_\{\\pi\_\{H\},\\pi\_\{A\}\}\\sum\_\{t=1\}^\{T\}r\_\{t\}\(\\pi\_\{H\},\\pi\_\{A\}\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\\right\)\.We decompose this into two terms by adding and subtracting the centralized algorithm’s reward:

RT\\displaystyle R\_\{T\}=α​maxπH,πA​∑t=1Trt​\(πH,πA\)−∑t=1Trt​\(π¯H\(t\),π¯A\(t\)\)⏟Rcentral\+∑t=1Trt​\(π¯H\(t\),π¯A\(t\)\)−∑t=1Trt​\(π¯H\(t\),πA\(t\)\)⏟Rcoord\.\\displaystyle=\\underbrace\{\\alpha\\max\_\{\\pi\_\{H\},\\pi\_\{A\}\}\\sum\_\{t=1\}^\{T\}r\_\{t\}\(\\pi\_\{H\},\\pi\_\{A\}\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\overline\{\\pi\}\_\{A\}^\{\(t\)\}\\right\)\}\_\{R\_\{\\text\{central\}\}\}\+\\underbrace\{\\sum\_\{t=1\}^\{T\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\overline\{\\pi\}\_\{A\}^\{\(t\)\}\\right\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\\right\)\}\_\{R\_\{\\text\{coord\}\}\}\.The first termRcentralR\_\{\\text\{central\}\}is the external regret of the centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}, i\.e\.,RTα,ext​\(AlgC\)R\_\{T\}^\{\\alpha,\\textrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\.

For the second term, letppdenote the number of times the sequence\(π¯H\(t\),π¯A\(t\)\)t=1T\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\overline\{\\pi\}\_\{A\}^\{\(t\)\}\\right\)\_\{t=1\}^\{T\}switches, and lets1,…,sps\_\{1\},\\ldots,s\_\{p\}be the time indices at which switches occur \(withs1=1s\_\{1\}=1andsp\+1=T\+1s\_\{p\+1\}=T\+1\)\. Within each segment\[si,si\+1\)\[s\_\{i\},s\_\{i\+1\}\), the centralized algorithm plays the same policy pair\. We can bound:

Rcoord\\displaystyle R\_\{\\text\{coord\}\}=∑t=1Trt​\(π¯H\(t\),π¯A\(t\)\)−∑t=1Trt​\(π¯H\(t\),πA\(t\)\)\\displaystyle=\\sum\_\{t=1\}^\{T\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\overline\{\\pi\}\_\{A\}^\{\(t\)\}\\right\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\\right\)=∑i=1p∑t=sisi\+1−1rt​\(π¯H\(si\),π¯A\(si\)\)−∑i=1p∑t=sisi\+1−1rt​\(π¯H\(si\),πA\(t\)\)\\displaystyle=\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(s\_\{i\}\)\},\\overline\{\\pi\}\_\{A\}^\{\(s\_\{i\}\)\}\\right\)\-\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(s\_\{i\}\)\},\\pi\_\{A\}^\{\(t\)\}\\right\)≤maxs1,…,spπA\(1\),…,πA\(p\)​∑i=1p∑t=sisi\+1−1\(rt​\(π¯H\(si\),πA\(i\)\)−rt​\(π¯H\(si\),πA\(t\)\)\)\\displaystyle\\leq\\max\_\{\\begin\{subarray\}\{c\}s\_\{1\},\\ldots,s\_\{p\}\\\\ \\pi\_\{A\}^\{\(1\)\},\\ldots,\\pi\_\{A\}^\{\(p\)\}\\end\{subarray\}\}\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}\\left\(r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(s\_\{i\}\)\},\\pi\_\{A\}^\{\(i\)\}\\right\)\-r\_\{t\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(s\_\{i\}\)\},\\pi\_\{A\}^\{\(t\)\}\\right\)\\right\)≤RTtrack​\(AlgA;p\)\.\\displaystyle\\leq R^\{\\text\{track\}\}\_\{T\}\(\\mathrm\{Alg\}\_\{A\};~p\)\.
Sincep≤ST​\(AlgC;δ\)p\\leq S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\delta\)with probability at least1−δ1\-\\delta, we have

RTα≤RTα,ext​\(AlgC\)\+RTtrack​\(AlgA;ST​\(AlgC;δ\)\)\+δ​T,R^\{\\alpha\}\_\{T\}\\leq R\_\{T\}^\{\\alpha,\\textrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\+R\_\{T\}^\{\\text\{track\}\}\(\\mathrm\{Alg\}\_\{A\};~S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\delta\)\)\+\\delta T,where theδ​T\\delta Tterm accounts for the event that the number of switches exceeds the high\-probability bound\. ∎

### D\.6Proof of[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)

From[Proposition˜E\.2](https://arxiv.org/html/2607.08012#A5.Thmtheorem2), the\(1−1/e\)\(1\-1/e\)\-approximate regret of the CR\-RAOCO algorithm is bounded by\(1−1/e\)\(1\-1/e\)times the regret of the underlying OCO algorithm\. By[Proposition˜E\.3](https://arxiv.org/html/2607.08012#A5.Thmtheorem3), the number of switches of CR\-RAOCO is at most the number of switches of the underlying OCO algorithm, since the coupled randomness makes the rounding step a deterministic function of the OCO iterate\.

We instantiate the inner OCO algorithm with the POMER algorithm ofAgarwal et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib1)\]\([Algorithm˜3](https://arxiv.org/html/2607.08012#alg3)\)\. The convex domain is𝒴=\[0,1\]MA​MH\\mathcal\{Y\}=\[0,1\]^\{M\_\{A\}M\_\{H\}\}, with diameterD=MA​MHD=\\sqrt\{M\_\{A\}M\_\{H\}\}and dimensiond=MA​MHd=M\_\{A\}M\_\{H\}\. By[Lemma˜D\.3](https://arxiv.org/html/2607.08012#A4.Thmtheorem3), the concave relaxationV~θ\\tilde\{V\}\_\{\\theta\}is11\-Lipschitz with respect to∥⋅∥1\\\|\\cdot\\\|\_\{1\}, henceGG\-Lipschitz with respect to∥⋅∥2\\\|\\cdot\\\|\_\{2\}forG≤MA​MHG\\leq\\sqrt\{M\_\{A\}M\_\{H\}\}\. Setting the switching budgetS=MA​MH​T​log⁡\(T\)S=\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log\(T\)in[Theorem˜E\.4](https://arxiv.org/html/2607.08012#A5.Thmtheorem4)gives

RT≤G​D​2​T\+16​G​D​log⁡\(T\)⋅d⋅TS\+13​G​D∈O​\(MA​MH​T\),R\_\{T\}\\;\\leq\\;GD\\sqrt\{2T\}\\;\+\\;16\\,GD\\log\(T\)\\cdot\\frac\{\\sqrt\{d\}\\cdot T\}\{S\}\\;\+\\;13\\,GD\\;\\in\\;O\\\!\\bigl\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\\bigr\),where the last bound substitutesG=D=MA​MHG=D=\\sqrt\{M\_\{A\}M\_\{H\}\},d=MA​MHd=M\_\{A\}M\_\{H\}, andS=MA​MH​T​log⁡\(T\)S=\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log\(T\), under which the middle term equals16​MA​MH​T16\\,M\_\{A\}M\_\{H\}\\sqrt\{T\}\. Multiplying by the\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)factor from[Proposition˜E\.2](https://arxiv.org/html/2607.08012#A5.Thmtheorem2)preserves the rate, giving the expected\(1−1/e\)\(1\-\\nicefrac\{\{1\}\}\{\{e\}\}\)\-approximate assistance regret bound stated in[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\.

For the switching bound,[Theorem˜E\.4](https://arxiv.org/html/2607.08012#A5.Thmtheorem4)givesPr⁡\[ST≥3​S\]≤e−S\\Pr\[S\_\{T\}\\geq 3S\]\\leq e^\{\-S\}\. ChoosingS=max⁡\(MA​MH​T​log⁡\(T\),log⁡\(1/δ\)\)S=\\max\\\!\\bigl\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log\(T\),~\\log\(1/\\delta\)\\bigr\)yields, with probability at least1−δ1\-\\delta,ST≤3​S∈O​\(MA​MH​T​log⁡\(T\)\+log⁡\(1/δ\)\)⊆O​\(MA​MH​T​log⁡\(T/δ\)\)S\_\{T\}\\leq 3S\\in O\\\!\\bigl\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log\(T\)\+\\log\(1/\\delta\)\\bigr\)\\subseteq O\\\!\\bigl\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log\(T/\\delta\)\\bigr\), matching the bound stated in[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\. By[Proposition˜E\.3](https://arxiv.org/html/2607.08012#A5.Thmtheorem3)this same bound applies to the number of switches made by CR\-RAOCO\.

Crucially,[Theorem˜E\.4](https://arxiv.org/html/2607.08012#A5.Thmtheorem4)requires only convexity and Lipschitz\-ness of the losses—both satisfied byV~θ\\tilde\{V\}\_\{\\theta\}—and does not require the smoothness assumption needed by FTPRLL\[Sherman and Koren,[2021](https://arxiv.org/html/2607.08012#bib.bib54)\], which fails for the piecewise\-linear value\-of\-assistance relaxation\. ∎

### D\.7Proof of[Proposition˜6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2)

We constructAlgA\\mathrm\{Alg\}\_\{A\}using an algorithmAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}as a subroutine in a blackbox manner\. We will chooseAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}to be an algorithm designed to minimize tracking regret in general online learning problems \(such as algorithms fromHerbster and Warmuth \[[1998](https://arxiv.org/html/2607.08012#bib.bib28)\], Cesa\-Bianchi et al\. \[[2012](https://arxiv.org/html/2607.08012#bib.bib8)\]\)\.

We will first describe howAlgA\\mathrm\{Alg\}\_\{A\}is constructed usingAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}\. Then we will express the tracking regret as ofAlgA\\mathrm\{Alg\}\_\{A\}in terms of tracking regret ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}\. Finally we will apply bounds on tracking regret from previous work to obtain the bound of the proposition\.

The assistant’s algorithmAlgA\\mathrm\{Alg\}\_\{A\}maintainsMHM\_\{H\}copies ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}, one for each human actionaH∈𝒜Ha\_\{H\}\\in\\mathcal\{A\}\_\{H\}\. Let us denote the copy associated with actionaHa\_\{H\}byAlgtrackaH\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}^\{a\_\{H\}\}\. Each copy ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}optimizes over the space of assistant actions𝒜A\\mathcal\{A\}\_\{A\}\. The assistant’s policy at roundtt:πA\(t\)\\pi\_\{A\}^\{\(t\)\}chooses the action selected by the copyAlgtrackaH\(t\)\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}^\{a\_\{H\}^\{\(t\)\}\}, whereaH\(t\)=πH\(t\)​\(θ\(t\)\)a\_\{H\}^\{\(t\)\}=\\pi\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\. At the end of roundtt, the assistant updates this copy ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}using the bandit feedback it receives of rewardrt​\(πH\(t\),πA\(t\)\)r\_\{t\}\(\\pi\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\)upon selecting actionaA\(t\)a\_\{A\}^\{\(t\)\}\.

We will show that we can bound the assistant’s tracking regret over the spaceΠA\\Pi\_\{A\}by the sum of the tracking regrets of each of theMHM\_\{H\}copies ofAlgtrack\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}\. We can decompose the rewardrtr\_\{t\}asrt​\(π¯H\(t\),πA\)=∑aH∈𝒜HrtaH​\(πA​\(aH\)\)r\_\{t\}\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\pi\_\{A\}\)=\\sum\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}r\_\{t\}^\{a\_\{H\}\}\(\\pi\_\{A\}\(a\_\{H\}\)\), where eachrtaH:𝒜A→\[0,1\]r\_\{t\}^\{a\_\{H\}\}:\\mathcal\{A\}\_\{A\}\\to\[0,1\]is defined byrtaH​\(aA\)=r​\(aH,aA;θ\(t\)\)⋅𝟏​\(π¯H\(t\)​\(θ\(t\)\)=aH\)r\_\{t\}^\{a\_\{H\}\}\(a\_\{A\}\)=r\(a\_\{H\},a\_\{A\};\\theta^\{\(t\)\}\)\\cdot\\mathbf\{1\}\\left\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)=a\_\{H\}\\right\)\.rtaHr\_\{t\}^\{a\_\{H\}\}is the reward function with which the copyAlgtrackaH\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}^\{a\_\{H\}\}is updated\. We can decompose the tracking regret of the assistant as

RTtrack​\(AlgA;p\)\\displaystyle R\_\{T\}^\{\\text\{track\}\}\(\\mathrm\{Alg\}\_\{A\};\\,p\)=maxs1,…,sp\+1πA\(1\),…,πA\(p\)∈ΠA​∑i=1p∑t=sisi\+1−1rt​\(π¯H\(t\),πA\(i\)\)−∑t=1Trt​\(π¯H\(t\),πA\(t\)\)\\displaystyle=\\max\_\{\\begin\{subarray\}\{c\}s\_\{1\},\\ldots,s\_\{p\+1\}\\\\ \\pi\_\{A\}^\{\(1\)\},\\ldots,\\pi\_\{A\}^\{\(p\)\}\\in\\Pi\_\{A\}\\end\{subarray\}\}\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}r\_\{t\}\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(i\)\}\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}\(\\overline\{\\pi\}\_\{H\}^\{\(t\)\},\\pi\_\{A\}^\{\(t\)\}\)=maxs1,…,sp\+1πA\(1\),…,πA\(p\)​∑aH∈𝒜H\[∑i=1p∑t=sisi\+1−1rtaH​\(πA\(i\)​\(aH\)\)−∑t=1TrtaH​\(πA\(t\)​\(aH\)\)\]\\displaystyle=\\max\_\{\\begin\{subarray\}\{c\}s\_\{1\},\\ldots,s\_\{p\+1\}\\\\ \\pi\_\{A\}^\{\(1\)\},\\ldots,\\pi\_\{A\}^\{\(p\)\}\\end\{subarray\}\}\\sum\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}\\left\[\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}r\_\{t\}^\{a\_\{H\}\}\(\\pi\_\{A\}^\{\(i\)\}\(a\_\{H\}\)\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}^\{a\_\{H\}\}\(\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\)\\right\]≤∑aH∈𝒜Hmaxs1,…,sp\+1πA\(1\),…,πA\(p\)⁡\[∑i=1p∑t=sisi\+1−1rtaH​\(πA\(i\)​\(aH\)\)−∑t=1TrtaH​\(πA\(t\)​\(aH\)\)\]\\displaystyle\\leq\\sum\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}\\max\_\{\\begin\{subarray\}\{c\}s\_\{1\},\\ldots,s\_\{p\+1\}\\\\ \\pi\_\{A\}^\{\(1\)\},\\ldots,\\pi\_\{A\}^\{\(p\)\}\\end\{subarray\}\}\\left\[\\sum\_\{i=1\}^\{p\}\\sum\_\{t=s\_\{i\}\}^\{s\_\{i\+1\}\-1\}r\_\{t\}^\{a\_\{H\}\}\(\\pi\_\{A\}^\{\(i\)\}\(a\_\{H\}\)\)\-\\sum\_\{t=1\}^\{T\}r\_\{t\}^\{a\_\{H\}\}\(\\pi\_\{A\}^\{\(t\)\}\(a\_\{H\}\)\)\\right\]≤∑aH∈𝒜HRTtrack​\(AlgtrackaH;p\)=MH​RTtrack​\(AlgtrackaH;p\)\.\\displaystyle\\leq\\sum\_\{a\_\{H\}\\in\\mathcal\{A\}\_\{H\}\}R\_\{T\}^\{\\text\{track\}\}\(\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}^\{a\_\{H\}\};\\,p\)=M\_\{H\}R\_\{T\}^\{\\text\{track\}\}\(\\mathrm\{Alg\}\_\{\\mathrm\{track\}\}^\{a\_\{H\}\};\\,p\)\.
Using regret bounds for a tracking regret minimizing algorithm from previous work like Fixed\-Share algorithm\[Herbster and Warmuth,[1998](https://arxiv.org/html/2607.08012#bib.bib28), Cesa\-Bianchi et al\.,[2012](https://arxiv.org/html/2607.08012#bib.bib8)\]that we restate in[Section˜E\.3](https://arxiv.org/html/2607.08012#A5.SS3), we get the tracking regret bound in the proposition\. ∎

### D\.8Proof of[Theorem˜4\.1](https://arxiv.org/html/2607.08012#S4.Thmtheorem1)

First we describe the decentralized human and assistant yielding this assistance regret rate\. The human algorithm is derived from the centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}with the external regret and switching bound provided in[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\. In particular,AlgC\\mathrm\{Alg\}\_\{C\}has expected\(1−1/e\)\(1\-1/e\)\-external regret at most𝒪​\(MA​MH​T\)\\mathcal\{O\}\\left\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\\right\)and, with probability1−1/T1\-\\nicefrac\{\{1\}\}\{\{T\}\}, switches at most𝒪​\(MA​MH​T​log⁡\(T\)\)\\mathcal\{O\}\\left\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\log\(T\)\\right\)times\.AlgH\\mathrm\{Alg\}\_\{H\}is derived fromAlgC\\mathrm\{Alg\}\_\{C\}in the standard way described in[Figure˜1](https://arxiv.org/html/2607.08012#S4.F1)\. The assistant algorithmAlgA\\mathrm\{Alg\}\_\{A\}is the one shown to achieve low tracking regret in[Proposition˜6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2)and the human algorithmAlgH\\mathrm\{Alg\}\_\{H\}derived from the centralized algorithm\.

We can immediately apply[Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)to achieve the regret guarantee stated in the theorem, forα=1−1/e\\alpha=1\-\\nicefrac\{\{1\}\}\{\{e\}\},

RTα\\displaystyle R\_\{T\}^\{\\alpha\}≤RTα,ext​\(AlgC\)\+RTtrack​\(AlgA;ST​\(AlgC;δ\)\)\+δ​T\\displaystyle\\leq R\_\{T\}^\{\\alpha,\\mathrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\+R\_\{T\}^\{\\mathrm\{track\}\}\(\\mathrm\{Alg\}\_\{A\};S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\delta\)\)\+\\delta T\(By[Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)\)\\displaystyle\(\\text\{By \\lx@cref\{creftypecap~refnum\}\{lem:stable\-adaptive\}\}\)=RTα,ext​\(AlgC\)\+MH​MA​T​log⁡\(MA​T\)⋅ST​\(AlgC;1/T\)\+1\\displaystyle=R\_\{T\}^\{\\alpha,\\mathrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\+M\_\{H\}\\sqrt\{M\_\{A\}T\\log\(M\_\{A\}T\)\\cdot S\_\{T\}\(\\mathrm\{Alg\}\_\{C\};\\nicefrac\{\{1\}\}\{\{T\}\}\)\}\+1\(By[Proposition˜6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2)\)\\displaystyle\(\\text\{By \\lx@cref\{creftypecap~refnum\}\{prop:black\-box\-tracking\-regret\}\}\)=MA​MH​T\+MH​MA​T​log⁡\(MA​T\)⋅MA​MH​T​log⁡\(T\)\+1\\displaystyle=M\_\{A\}M\_\{H\}\\sqrt\{T\}\+M\_\{H\}\\sqrt\{M\_\{A\}T\\log\(M\_\{A\}T\)\\cdot\\sqrt\{M\_\{A\}M\_\{H\}T\}\\log\(T\)\}\+1\(By[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\)\\displaystyle\(\\text\{By \\lx@cref\{creftypecap~refnum\}\{prop:stable\-centralized\}\}\)∈𝒪​\(MA​MH​T\+MH5/4​MA3/4​T3/4​log⁡\(MA​T\)​log⁡\(T\)\)⊆𝒪​\(MA​MH​T\+MH5/4​MA3/4​log⁡\(MA​T\)​T3/4\)\.\\displaystyle\\in\\mathcal\{O\}\\left\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\+M\_\{H\}^\{5/4\}M\_\{A\}^\{3/4\}\\,T^\{3/4\}\\sqrt\{\\log\(M\_\{A\}T\)\\log\(T\)\}\\right\)\\subseteq\\mathcal\{O\}\\left\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\+M\_\{H\}^\{5/4\}M\_\{A\}^\{3/4\}\\log\(M\_\{A\}T\)\\,T^\{3/4\}\\right\)\.∎

### D\.9Proof of[Theorem˜4\.2](https://arxiv.org/html/2607.08012#S4.Thmtheorem2)

We first describe the human and assistant algorithmsAlgH\\mathrm\{Alg\}\_\{H\}andAlgA\\mathrm\{Alg\}\_\{A\}, and then bound their assistance regret\.

#### Construction ofAlgH\\mathrm\{Alg\}\_\{H\}andAlgA\\mathrm\{Alg\}\_\{A\}\.

As in the proofs of[Lemmas˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)and[6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2), the human algorithmAlgH\\mathrm\{Alg\}\_\{H\}runs the stable centralized algorithmAlgC\\mathrm\{Alg\}\_\{C\}from[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1)\. On most rounds it plays the human component ofAlgC\\mathrm\{Alg\}\_\{C\}’s output\. However, wheneverAlgC\\mathrm\{Alg\}\_\{C\}switches to a new policy pair,AlgH\\mathrm\{Alg\}\_\{H\}temporarily deviates in order to communicate the new assistant policy to the assistant\. This removes the need for the assistant to relearn the policy through exploration, enabling us to get a better regret rate than theO​\(T3/4\)O\(T^\{3/4\}\)rate in[Proposition˜6\.2](https://arxiv.org/html/2607.08012#S6.Thmtheorem2)\.

An assistant policy is a mappingπA:𝒜H→𝒜A\\pi\_\{A\}:\\mathcal\{A\}\_\{H\}\\to\\mathcal\{A\}\_\{A\}\. There areMAMHM\_\{A\}^\{M\_\{H\}\}such policies, so any policy can be encoded usinglogMH⁡\(MAMH\)=MH​logMH⁡\(MA\)\\log\_\{M\_\{H\}\}\(M\_\{A\}^\{M\_\{H\}\}\)=M\_\{H\}\\log\_\{M\_\{H\}\}\(M\_\{A\}\)human actions\. We assume the agents share a common mapping sequences of human actions to assistant policies\.

#### Signaling a switch\.

To begin communication, both agents must detect that a switch has occurred\. The human knows this \(since it runsAlgC\\mathrm\{Alg\}\_\{C\}\), but the assistant does not\. We design the following signaling\-string protocol in which the human uses a special sequence of actions to indicate that a switch has occurred\.

Before the first round of the game, but after nature chooses a sequence of preferences\(θ\(1\),…,θ\(T\)\)\(\\theta^\{\(1\)\},\\dots,\\theta^\{\(T\)\}\), the human and assistant sample a shared random stringσ∈𝒜Hℓ\\sigma\\in\\mathcal\{A\}\_\{H\}^\{\\ell\}, forℓ=⌈2​logMH⁡T⌉\\ell=\\left\\lceil 2\\log\_\{M\_\{H\}\}T\\right\\rceil, where each element ofσ\\sigmathat is drawn uniformly at random from𝒜H\\mathcal\{A\}\_\{H\}\. The human chooses actions according to stringσ\\sigmato indicate to the assistant the start of a communication phase\.

Let us call the rounds outside of the communication and signaling stringσ\\sigmarounds of normal play\. These are rounds where the human’s action is derived from the centralized algorithm\. That is,aH\(t\)=π¯H\(t\)​\(θ\(t\)\)a\_\{H\}^\{\(t\)\}=\\overline\{\\pi\}\_\{H\}^\{\(t\)\}\(\\theta^\{\(t\)\}\)\.

WheneverAlgC\\mathrm\{Alg\}\_\{C\}switches to a new policy pair, the human instead plays 1\) the signaling stringσ\\sigmaforℓ\\ellrounds, and 2\) the encoded assistant policy forMH​logMH⁡\(MA\)M\_\{H\}\\log\_\{M\_\{H\}\}\(M\_\{A\}\)rounds\. The assistant monitors a sliding window of the lastℓ\\ellhuman actions and, upon detectingσ\\sigma, interprets the subsequentMH​logMH⁡\(MA\)M\_\{H\}\\log\_\{M\_\{H\}\}\(M\_\{A\}\)actions as an encoding of the new assistant policy\.

#### No false positives in assistant’s detection of communication phase\.

We now show it is unlikely that the assistant incorrectly perceives the start of a communication phase\. That isσ\\sigmais unlikely to appear accidentally during normal play\.

Because the adversary is oblivious, the sequence\(θ\(1\),…,θ\(T\)\)\(\\theta^\{\(1\)\},\\dots,\\theta^\{\(T\)\}\)is fixed beforeσ\\sigmais sampled\. Moreover,AlgC\\mathrm\{Alg\}\_\{C\}is full\-information: its updates depend only on past preferences and its own randomness, and not on the realized actions\. Fix any realizationρ\\rhoofAlgC\\mathrm\{Alg\}\_\{C\}’s internal randomness\. Given\(θ\(1\),…,θ\(T\)\)\(\\theta^\{\(1\)\},\\dots,\\theta^\{\(T\)\}\)andρ\\rho, the sequence of policies output byAlgC\\mathrm\{Alg\}\_\{C\}is deterministic\. Hence the sequence of human actions during normal play𝐚𝐇norm​\(ρ\)\\mathbf\{a\_\{H\}\}^\{\\mathrm\{norm\}\}\(\\rho\)is deterministic and does not depend onσ\\sigma\.

Sinceσ\\sigmais drawn uniformly from𝒜Hℓ\\mathcal\{A\}\_\{H\}^\{\\ell\}and independently of𝐚norm​\(ρ\)\\mathbf\{a\}^\{\\mathrm\{norm\}\}\(\\rho\), the probability that any fixed window ofℓ\\ellconsecutive normal\-play actions equalsσ\\sigmaisMH−ℓM\_\{H\}^\{\-\\ell\}\. Taking a union bound over at mostTTsuch windows,

Pr⁡\[σ​appears during normal play\]≤T⋅MH−ℓ≤T⋅T−2=1T\.\\Pr\\left\[\\sigma\\text\{ appears during normal play\}\\right\]\\leq T\\cdot M\_\{H\}^\{\-\\ell\}\\leq T\\cdot T^\{\-2\}=\\frac\{1\}\{T\}\.This bound holds for everyρ\\rho, and hence unconditionally\. Therefore, with probability at least1−1/T1\-1/T, the assistant detects every communication phase correctly and incurs no false positives\.

After receiving a communicated policy, the assistant plays it exactly until the next switch, achieving perfect synchronization\.

#### Assistance regret analysis\.

To get the final bound on assistance regret, we will use an approach similar to the decomposition from[Lemma˜4\.4](https://arxiv.org/html/2607.08012#S4.Thmtheorem4)\. Conditioning on the event thatσ\\sigmadoes not appear during normal play \(which holds with probability at least1−1/T1\-1/T\), the policies played by the decentralized algorithms match the policies selected byAlgC\\mathrm\{Alg\}\_\{C\}in all rounds but 1\) the rounds where signaling stringσ\\sigmais played to indicate switch, and 2\) the rounds used to communicate the switched assistant policy\. For a single switch, these rounds occurℓ=logMH⁡T\\ell=\\log\_\{M\_\{H\}\}Ttimes andMH​logMH⁡MAM\_\{H\}\\log\_\{M\_\{H\}\}M\_\{A\}times respectively\. Since rewards lie in\[0,1\]\[0,1\], each such round incurs at most unit regret\. IfAlgC\\mathrm\{Alg\}\_\{C\}makesSTS\_\{T\}switches, then these rounds result in a cost of coordination of

Rcoord≤\(ℓ\+MH​logMH⁡\(MA\)\)​ST=O​\(MH​logMH⁡\(MA\)\+logMH⁡T\)​ST\.R\_\{\\mathrm\{coord\}\}\\leq\(\\ell\+M\_\{H\}\\log\_\{M\_\{H\}\}\(M\_\{A\}\)\)\\,S\_\{T\}=O\\\!\\bigl\(M\_\{H\}\\log\_\{M\_\{H\}\}\(M\_\{A\}\)\+\\log\_\{M\_\{H\}\}T\\bigr\)\\,S\_\{T\}\.
On the1/T1/T\-probability event of a false positive, we bound regret byTT, contributing at most11in expectation\.

By[Proposition˜6\.1](https://arxiv.org/html/2607.08012#S6.Thmtheorem1), the centralized algorithm satisfies

RText​\(AlgC\)∈O​\(MA​MH​T\),ST∈O​\(MA​MH​T​log⁡\(T/δ\)\)R\_\{T\}^\{\\mathrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\\in O\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\),\\qquad S\_\{T\}\\in O\\\!\\bigl\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log\(T/\\delta\)\\bigr\)with probability at least1−δ1\-\\delta\. Settingδ=1/T\\delta=1/Tand combining terms,

RT\\displaystyle R\_\{T\}≤RText​\(AlgC\)\+Rcoord\+δ​T\\displaystyle\\leq R\_\{T\}^\{\\mathrm\{ext\}\}\(\\mathrm\{Alg\}\_\{C\}\)\+R\_\{\\mathrm\{coord\}\}\+\\delta T≤O​\(MA​MH​T\)\+O​\(MH​logMH⁡\(MA\)\+logMH⁡T\)⋅O​\(MA​MH​T​log⁡T\)\+O​\(1\)\\displaystyle\\leq O\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\)\+O\\\!\\bigl\(M\_\{H\}\\log\_\{M\_\{H\}\}\(M\_\{A\}\)\+\\log\_\{M\_\{H\}\}T\\bigr\)\\cdot O\\\!\\bigl\(\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log T\\bigr\)\+O\(1\)=O​\(MA​MH​T\+\(MH​log⁡MA\+log⁡T\)​MA​MH​T​log⁡T\)⊆𝒪​\(MA​MH​T\+MH​MH​MA​T​log⁡\(MA​T\)​log⁡T\)\.\\displaystyle=O\\\!\\bigl\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\+\(M\_\{H\}\\log M\_\{A\}\+\\log T\)\\,\\sqrt\{M\_\{A\}M\_\{H\}T\}\\,\\log T\\bigr\)\\subseteq\\mathcal\{O\}\\left\(M\_\{A\}M\_\{H\}\\sqrt\{T\}\+M\_\{H\}\\sqrt\{M\_\{H\}M\_\{A\}T\}\\,\\log\(M\_\{A\}T\)\\log T\\right\)\.

## Appendix EResults from Previous Work

In this section, we will state the results from previous work that we use for our results\. We will also prove any extensions to these results that we need for our results\.

### E\.1Online Submodular Maximization

A key tool that we use is the reduction of online submodular maximization to online convex optimization constructed inSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]\. This reduction relies on the existence of concave relaxations and rounding schemes that satisfy a “sandwich property\.” The following proposition establishes that this property holds for Lipschitz weighted threshold potentials \([Definition˜A\.2](https://arxiv.org/html/2607.08012#A1.Thmtheorem2)\), which is the class of functions arising in assistance games\.

###### Proposition E\.1\(Sandwich Property for Lipschitz Weighted Threshold Potentials\)\.

Let𝒳⊆\{0,1\}n\\mathcal\{X\}\\subseteq\\\{0,1\\\}^\{n\}and let𝒴=conv​\(𝒳\)\\mathcal\{Y\}=\\mathrm\{conv\}\(\\mathcal\{X\}\)be its convex hull\. Letℱ\\mathcal\{F\}be a class of weighted threshold potential functions \([Definition˜A\.2](https://arxiv.org/html/2607.08012#A1.Thmtheorem2)\) over𝒳\\mathcal\{X\}that areLL\-Lipschitz\. Then, there exists a randomized roundingΞ:𝒴×U→𝒳\\Xi:\\mathcal\{Y\}\\times U\\to\\mathcal\{X\}, whereUUis a random variable, such that for everyf∈ℱf\\in\\mathcal\{F\}, there exists anLL\-Lipschitz concave functionf~:𝒴→ℝ\\tilde\{f\}:\\mathcal\{Y\}\\to\\mathbb\{R\}satisfying:

1. 1\.f~​\(𝐱\)≥f​\(𝐱\)\\tilde\{f\}\(\\mathbf\{x\}\)\\geq f\(\\mathbf\{x\}\)for all𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}, and
2. 2\.𝔼Ξ​\[f​\(Ξ​\(𝐲\)\)\]≥\(1−1/e\)⋅f~​\(𝐲\)\\mathbb\{E\}\_\{\\Xi\}\[f\(\\Xi\(\\mathbf\{y\}\)\)\]\\geq\(1\-1/e\)\\cdot\\tilde\{f\}\(\\mathbf\{y\}\)for all𝐲∈𝒴\\mathbf\{y\}\\in\\mathcal\{Y\}\.

This proposition is stated as Lemma 1 inSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]and its proof is provided in Appendix E ofSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]\. The proof involves showing that negatively correlated randomized roundings lead to the property stated in the proposition for weighted threshold potential functions with concave relaxations that are Lipschitz\. It then uses results fromChekuri et al\. \[[2010](https://arxiv.org/html/2607.08012#bib.bib10)\]to show that swap rounding and randomized pipage rounding are negatively correlated for partition matroidsℳ\\mathcal\{M\}\. We describe the swap rounding algorithm and express it as a function over𝒳\\mathcal\{X\}and a random variableU∼Uniform​\(\[0,1\]\)n\+1U\\sim\\mathrm\{Uniform\}\(\[0,1\]\)^\{n\+1\}\.

Algorithm 1Swap Rounding\[Chekuri et al\.,[2010](https://arxiv.org/html/2607.08012#bib.bib10), Salem et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]1:

𝐲∈𝒴=conv​\(𝒳\)\\mathbf\{y\}\\in\\mathcal\{Y\}=\\mathrm\{conv\}\(\\mathcal\{X\}\), random vector

𝐔=\(U1,…,Un\+1\)∼Unif​\(\[0,1\]\)n\+1\\mathbf\{U\}=\(U\_\{1\},\\ldots,U\_\{n\+1\}\)\\sim\\mathrm\{Unif\}\(\[0,1\]\)^\{n\+1\}
2:

𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}
3:Decompose

𝐲=∑k=1Kγk​𝐳k\\mathbf\{y\}=\\sum\_\{k=1\}^\{K\}\\gamma\_\{k\}\\mathbf\{z\}\_\{k\}where

γk∈\[0,1\]\\gamma\_\{k\}\\in\[0,1\],

∑k=1Kγk=1\\sum\_\{k=1\}^\{K\}\\gamma\_\{k\}=1, and

𝐳k∈𝒳\\mathbf\{z\}\_\{k\}\\in\\mathcal\{X\}are bases of the matroid⊳\\trianglerightK≤n\+1K\\leq n\+1by Carathéodory

4:

β1←γ1\\beta\_\{1\}\\leftarrow\\gamma\_\{1\}
5:

𝐱←𝐳1\\mathbf\{x\}\\leftarrow\\mathbf\{z\}\_\{1\}
6:for

k=1,…,K−1k=1,\\ldots,K\-1do

7:

βk\+1←βk\+γk\+1\\beta\_\{k\+1\}\\leftarrow\\beta\_\{k\}\+\\gamma\_\{k\+1\}
8:if

Uk≤βk/βk\+1U\_\{k\}\\leq\\beta\_\{k\}/\\beta\_\{k\+1\}then

9:

𝐱←𝐱\\mathbf\{x\}\\leftarrow\\mathbf\{x\}⊳\\trianglerightProbabilityβk/βk\+1\\beta\_\{k\}/\\beta\_\{k\+1\}: keep current

10:else

11:

𝐱←𝐳k\+1\\mathbf\{x\}\\leftarrow\\mathbf\{z\}\_\{k\+1\}⊳\\trianglerightProbabilityγk\+1/βk\+1\\gamma\_\{k\+1\}/\\beta\_\{k\+1\}: switch

12:endif

13:endfor

14:return

𝐱\\mathbf\{x\}

The algorithm provided bySalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]using this reduction is called Randomness Augmented Online Convex Optimization \(RAOCO\)\. We use a slightly modified version called the Coupled\-Randomness RAOCO \(CR\-RAOCO\) algorithm\. CR\-RAOCO implements the RAOCO algorithm inSalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]but by coupling the randomness in the rounding step across the different rounds\. This is done by drawing a single random variable𝐔∼Uniform​\(\[0,1\]\)n\+1\\mathbf\{U\}\\sim\\mathrm\{Uniform\}\(\[0,1\]\)^\{n\+1\}and using it to round all the points across all the rounds\. We introduce the coupling to enhance the stability of the RAOCO algorithm\. We provide a description of the CR\-RAOCO algorithm in the following algorithm[Algorithm˜2](https://arxiv.org/html/2607.08012#alg2)\.

Algorithm 2Coupled\-Randomness RAOCO \(CR\-RAOCO\)1:OCO policy

𝒫𝒴\\mathcal\{P\}\_\{\\mathcal\{Y\}\}, randomized rounding

Ξ:𝒴×U→𝒳\\Xi:\\mathcal\{Y\}\\times U\\to\\mathcal\{X\}, randomness distribution

𝒟r​a​n​d​o​m\\mathcal\{D\}\_\{random\}
2:

𝐔∼𝒟r​a​n​d​o​m\\mathbf\{U\}\\sim\\mathcal\{D\}\_\{random\}⊳\\trianglerightSample randomness once

3:for

t=1,2,…,Tt=1,2,\\ldots,Tdo

4:

𝐲t←𝒫𝒴,t​\(\(𝐲s\)s<t,\(f~s\)s<t\)\\mathbf\{y\}\_\{t\}\\leftarrow\\mathcal\{P\}\_\{\\mathcal\{Y\},t\}\(\(\\mathbf\{y\}\_\{s\}\)\_\{s<t\},\(\\tilde\{f\}\_\{s\}\)\_\{s<t\}\)
5:

𝐱t←Ξ​\(𝐲t,𝐔\)\\mathbf\{x\}\_\{t\}\\leftarrow\\Xi\(\\mathbf\{y\}\_\{t\},\\mathbf\{U\}\)⊳\\trianglerightRound using shared randomness𝐔\\mathbf\{U\}

6:Play

𝐱t\\mathbf\{x\}\_\{t\}and receive reward

ft​\(𝐱t\)f\_\{t\}\(\\mathbf\{x\}\_\{t\}\)
7:Reward function

ftf\_\{t\}is revealed

8:Construct concave extension

f~t\\tilde\{f\}\_\{t\}from

ftf\_\{t\}as in[Proposition˜E\.1](https://arxiv.org/html/2607.08012#A5.Thmtheorem1)

9:endfor

The following proposition shows that the regret of the CR\-RAOCO policy transfers from the OCO regret guarantee\. The analysis is basically the same as the regret analysis of RAOCO done bySalem et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]\. The only difference is establishing that the sandwich property shown in[Proposition˜E\.1](https://arxiv.org/html/2607.08012#A5.Thmtheorem1)holds with the coupled rounding procedure as well\. The sandwich property is only a condition on the expectation of a function applied to the rounded random variable\. Since the marginal distribution of the rounded random variable is unchanged after the coupling, the expectation remains the same and the property continues to hold\. We state the regret analysis including this additional argument below\.

###### Proposition E\.2\(Regret Bound for RAOCO\[Salem et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib51)\]\)\.

Under the Sandwich Property \([Proposition˜E\.1](https://arxiv.org/html/2607.08012#A5.Thmtheorem1)\), given an OCO policy𝒫𝒴\\mathcal\{P\}\_\{\\mathcal\{Y\}\}operating over𝒴=conv​\(𝒳\)\\mathcal\{Y\}=\\mathrm\{conv\}\(\\mathcal\{X\}\), the RAOCO policy𝒫𝒳\\mathcal\{P\}\_\{\\mathcal\{X\}\}described by[Algorithm˜2](https://arxiv.org/html/2607.08012#alg2)satisfies

α​\-​regretT​\(𝒫𝒳\)≤α⋅regretT​\(𝒫𝒴\)\.\\alpha\\text\{\-\}\\mathrm\{regret\}\_\{T\}\(\\mathcal\{P\}\_\{\\mathcal\{X\}\}\)\\leq\\alpha\\cdot\\mathrm\{regret\}\_\{T\}\(\\mathcal\{P\}\_\{\\mathcal\{Y\}\}\)\.

###### Proof\.

Consider the sequence of reward functions\{f1,f2,…,fT\}∈ℱT\\\{f\_\{1\},f\_\{2\},\\ldots,f\_\{T\}\\\}\\in\\mathcal\{F\}^\{T\}and the associated sequence of concave relaxations\{f~1,f~2,…,f~T\}∈ℱ~T\\\{\\tilde\{f\}\_\{1\},\\tilde\{f\}\_\{2\},\\ldots,\\tilde\{f\}\_\{T\}\\\}\\in\\tilde\{\\mathcal\{F\}\}^\{T\}\. Then,

max𝐱∈𝒳​∑t=1Tft​\(𝐱\)≤max𝐱∈𝒳​∑t=1Tf~t​\(𝐱\)≤max𝐲∈𝒴​∑t=1Tf~t​\(𝐲\)\.\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\)\\leq\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}\\tilde\{f\}\_\{t\}\(\\mathbf\{x\}\)\\leq\\max\_\{\\mathbf\{y\}\\in\\mathcal\{Y\}\}\\sum\_\{t=1\}^\{T\}\\tilde\{f\}\_\{t\}\(\\mathbf\{y\}\)\.\(6\)The first inequality follows from the upper bound propertyf~​\(𝐱\)≥f​\(𝐱\)\\tilde\{f\}\(\\mathbf\{x\}\)\\geq f\(\\mathbf\{x\}\)for all𝐱∈𝒳\\mathbf\{x\}\\in\\mathcal\{X\}\(property 1 in[Proposition˜E\.1](https://arxiv.org/html/2607.08012#A5.Thmtheorem1)\), and the second inequality holds because maximizing over a superset𝒴=conv​\(𝒳\)⊇𝒳\\mathcal\{Y\}=\\mathrm\{conv\}\(\\mathcal\{X\}\)\\supseteq\\mathcal\{X\}can only increase the objective value attained\.

The total expected reward obtained by the RAOCO policy is given by

𝔼Ξ​\[∑t=1Tft​\(𝐱t\)\]=∑t=1T𝔼Ξ​\[ft​\(𝐱t\)\]=∑t=1T𝔼Ξ​\[ft​\(Ξ​\(𝐲t\)\)\]≥α​∑t=1Tf~t​\(𝐲t\),\\mathbb\{E\}\_\{\\Xi\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\_\{t\}\)\\right\]=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{\\Xi\}\[f\_\{t\}\(\\mathbf\{x\}\_\{t\}\)\]=\\sum\_\{t=1\}^\{T\}\\mathbb\{E\}\_\{\\Xi\}\[f\_\{t\}\(\\Xi\(\\mathbf\{y\}\_\{t\}\)\)\]\\geq\\alpha\\sum\_\{t=1\}^\{T\}\\tilde\{f\}\_\{t\}\(\\mathbf\{y\}\_\{t\}\),\(7\)where the inequality follows from the rounding property𝔼Ξ​\[f​\(Ξ​\(𝐲\)\)\]≥α⋅f~​\(𝐲\)\\mathbb\{E\}\_\{\\Xi\}\[f\(\\Xi\(\\mathbf\{y\}\)\)\]\\geq\\alpha\\cdot\\tilde\{f\}\(\\mathbf\{y\}\)for all𝐲∈𝒴\\mathbf\{y\}\\in\\mathcal\{Y\}\(property 2 in[Proposition˜E\.1](https://arxiv.org/html/2607.08012#A5.Thmtheorem1)\)\.

Combining[Equations˜6](https://arxiv.org/html/2607.08012#A5.E6)and[7](https://arxiv.org/html/2607.08012#A5.E7), we obtain

α​max𝐱∈𝒳​∑t=1Tft​\(𝐱\)−𝔼Ξ​\[∑t=1Tft​\(𝐱t\)\]\\displaystyle\\alpha\\max\_\{\\mathbf\{x\}\\in\\mathcal\{X\}\}\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\)\-\\mathbb\{E\}\_\{\\Xi\}\\left\[\\sum\_\{t=1\}^\{T\}f\_\{t\}\(\\mathbf\{x\}\_\{t\}\)\\right\]≤α​max𝐲∈𝒴​∑t=1Tf~t​\(𝐲\)−α​∑t=1Tf~t​\(𝐲t\)\.\\displaystyle\\leq\\alpha\\max\_\{\\mathbf\{y\}\\in\\mathcal\{Y\}\}\\sum\_\{t=1\}^\{T\}\\tilde\{f\}\_\{t\}\(\\mathbf\{y\}\)\-\\alpha\\sum\_\{t=1\}^\{T\}\\tilde\{f\}\_\{t\}\(\\mathbf\{y\}\_\{t\}\)\.
Taking the supremum over all sequences of reward functions inℱT\\mathcal\{F\}^\{T\}on both sides yields the desired result:

α​\-​regretT​\(𝒫𝒳\)≤α⋅regretT​\(𝒫𝒴\)\.\\alpha\\text\{\-\}\\mathrm\{regret\}\_\{T\}\(\\mathcal\{P\}\_\{\\mathcal\{X\}\}\)\\leq\\alpha\\cdot\\mathrm\{regret\}\_\{T\}\(\\mathcal\{P\}\_\{\\mathcal\{Y\}\}\)\.∎

The following proposition establishes that the number of switches made by CR\-RAOCO is exactly the number of switches made by the underlying OCO policy\. This is a key property that allows us to control the switching cost of the algorithm\.

###### Proposition E\.3\(Switching Bound for CR\-RAOCO\)\.

Let𝒫𝒴\\mathcal\{P\}\_\{\\mathcal\{Y\}\}be an OCO policy and let𝒫𝒳\\mathcal\{P\}\_\{\\mathcal\{X\}\}be the CR\-RAOCO policy described by[Algorithm˜2](https://arxiv.org/html/2607.08012#alg2)\. Let\(𝐲1,…,𝐲T\)\(\\mathbf\{y\}\_\{1\},\\ldots,\\mathbf\{y\}\_\{T\}\)be the sequence of fractional points produced by𝒫𝒴\\mathcal\{P\}\_\{\\mathcal\{Y\}\}and let\(𝐱1,…,𝐱T\)\(\\mathbf\{x\}\_\{1\},\\ldots,\\mathbf\{x\}\_\{T\}\)be the sequence of integral points produced by𝒫𝒳\\mathcal\{P\}\_\{\\mathcal\{X\}\}\. Then, the number of switches satisfies

∑t=2T𝟙​\[𝐱t≠𝐱t−1\]≤∑t=2T𝟙​\[𝐲t≠𝐲t−1\]\.\\sum\_\{t=2\}^\{T\}\\mathbbm\{1\}\[\\mathbf\{x\}\_\{t\}\\neq\\mathbf\{x\}\_\{t\-1\}\]\\leq\\sum\_\{t=2\}^\{T\}\\mathbbm\{1\}\[\\mathbf\{y\}\_\{t\}\\neq\\mathbf\{y\}\_\{t\-1\}\]\.

###### Proof\.

In CR\-RAOCO, the randomness𝐔\\mathbf\{U\}is sampled once at the beginning and shared across all rounds\. Given this fixed𝐔\\mathbf\{U\}, the rounding functionΞ​\(⋅,𝐔\):𝒴→𝒳\\Xi\(\\cdot,\\mathbf\{U\}\):\\mathcal\{Y\}\\to\\mathcal\{X\}is a deterministic function\. Therefore,𝐱t=Ξ​\(𝐲t,𝐔\)\\mathbf\{x\}\_\{t\}=\\Xi\(\\mathbf\{y\}\_\{t\},\\mathbf\{U\}\)for alltt\.

SinceΞ​\(⋅,𝐔\)\\Xi\(\\cdot,\\mathbf\{U\}\)is deterministic, if𝐲t=𝐲t−1\\mathbf\{y\}\_\{t\}=\\mathbf\{y\}\_\{t\-1\}, then𝐱t=Ξ​\(𝐲t,𝐔\)=Ξ​\(𝐲t−1,𝐔\)=𝐱t−1\\mathbf\{x\}\_\{t\}=\\Xi\(\\mathbf\{y\}\_\{t\},\\mathbf\{U\}\)=\\Xi\(\\mathbf\{y\}\_\{t\-1\},\\mathbf\{U\}\)=\\mathbf\{x\}\_\{t\-1\}\. Equivalently,𝐱t≠𝐱t−1\\mathbf\{x\}\_\{t\}\\neq\\mathbf\{x\}\_\{t\-1\}implies𝐲t≠𝐲t−1\\mathbf\{y\}\_\{t\}\\neq\\mathbf\{y\}\_\{t\-1\}\. Thus,

𝟙​\[𝐱t≠𝐱t−1\]≤𝟙​\[𝐲t≠𝐲t−1\]\\mathbbm\{1\}\[\\mathbf\{x\}\_\{t\}\\neq\\mathbf\{x\}\_\{t\-1\}\]\\leq\\mathbbm\{1\}\[\\mathbf\{y\}\_\{t\}\\neq\\mathbf\{y\}\_\{t\-1\}\]for allt≥2t\\geq 2, and summing overttyields the result\. ∎

### E\.2Online Convex Optimization with Few Switches

The CR\-RAOCO algorithm uses an OCO algorithm as a black box\. To ensure CR\-RAOCO has both low regret and few switches, we use the Private Continuous Online Multiplicative Weights with Euclidean Regularization \(POMER\) algorithm ofAgarwal et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib1)\], a Shrinking\-Dartboard\-style algorithm based on sampling from a strongly log\-concave density\. Unlike the lazy OCO algorithm ofSherman and Koren \[[2021](https://arxiv.org/html/2607.08012#bib.bib54)\], which requires the loss functions to beβ\\beta\-smooth, POMER requires only that the losses be convex and Lipschitz—properties that hold for the value\-of\-assistance concave relaxationV~θ\\tilde\{V\}\_\{\\theta\}used in our setting \([Lemma˜D\.3](https://arxiv.org/html/2607.08012#A4.Thmtheorem3)\)\. Compared to the earlier Shrinking\-Dartboard variant ofAnava et al\. \[[2015](https://arxiv.org/html/2607.08012#bib.bib4)\], POMER additionally provides a flexible switching budget, an improved dimensional dependence in its regret bound, and a high\-probability bound on the number of switches that is included directly in the analysis ofAgarwal et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib1)\]\.

Algorithm 3Private Continuous Online Multiplicative Weights with Euclidean Regularization \(POMER\)\[Agarwal et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib1)\]1:Convex domain

W⊆ℝdW\\subseteq\\mathbb\{R\}^\{d\}, temperature

β\>0\\beta\>0, regularization

λ\>0\\lambda\>0, scale

Φ\>0\\Phi\>0
2:Sample

x1∼μ1x\_\{1\}\\sim\\mu\_\{1\}where

μ1​\(x\)∝exp⁡\(−λ2​‖x‖2\)\\mu\_\{1\}\(x\)\\propto\\exp\\\!\\bigl\(\-\\tfrac\{\\lambda\}\{2\}\\\|x\\\|^\{2\}\\bigr\)
3:for

t=1,…,Tt=1,\\ldots,Tdo

4:Play

xtx\_\{t\}and observe loss

gt:W→\[0,1\]g\_\{t\}:W\\to\[0,1\]
5:Define the strongly log\-concave density

μt\+1​\(x\)∝exp⁡\(−β​∑τ=1tgτ​\(x\)−λ2​‖x‖2\)\\mu\_\{t\+1\}\(x\)\\propto\\exp\\\!\\Bigl\(\-\\beta\\sum\_\{\\tau=1\}^\{t\}g\_\{\\tau\}\(x\)\-\\tfrac\{\\lambda\}\{2\}\\\|x\\\|^\{2\}\\Bigr\)
6:With probability

min⁡\{1,μt\+1​\(xt\)/\(Φ⋅μt​\(xt\)\)\}\\min\\\!\\bigl\\\{1,~\\mu\_\{t\+1\}\(x\_\{t\}\)/\(\\Phi\\cdot\\mu\_\{t\}\(x\_\{t\}\)\)\\bigr\\\}, set

xt\+1←xtx\_\{t\+1\}\\leftarrow x\_\{t\}⊳\\trianglerightStay

7:Otherwise, sample

xt\+1∼μt\+1x\_\{t\+1\}\\sim\\mu\_\{t\+1\}independently⊳\\trianglerightSwitch

8:endfor

POMER samples each iterate from a strongly log\-concave density—continuous online multiplicative weights with an addedℓ2\\ell\_\{2\}regularization—and uses a rejection\-sampling\-style stay\-step that ensures few switches while preserving the marginal regret of the underlying continuous multiplicative weights distribution\. The strong\-convexity term governed byλ\\lambdais the key innovation that buys the improved dimensional dependence relative to prior non\-smooth analyses\. The following theorem fromAgarwal et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib1)\]bounds both the regret and the number of switches as a function of an arbitrary switching budgetSS, with no smoothness assumption on the losses\.

###### Theorem E\.4\(Lazy OCO Guarantees\[Agarwal et al\.,[2024](https://arxiv.org/html/2607.08012#bib.bib1)\]\)\.

LetW⊆ℝdW\\subseteq\\mathbb\{R\}^\{d\}be convex with diameterD=supx,y∈W‖x−y‖D=\\sup\_\{x,y\\in W\}\\\|x\-y\\\|, and letg1,…,gT:W→\[0,1\]g\_\{1\},\\ldots,g\_\{T\}:W\\to\[0,1\]be convex andGG\-Lipschitz\. For any switching budgetS∈\[1,T\]S\\in\[1,T\], with parametersβ,λ,Φ\\beta,\\lambda,\\Phichosen as in Theorem 4\.5 ofAgarwal et al\. \[[2024](https://arxiv.org/html/2607.08012#bib.bib1)\],[Algorithm˜3](https://arxiv.org/html/2607.08012#alg3)satisfies

RT≤G​D​2​T\+16​G​D​log⁡\(T\)⋅d⋅TS\+13​G​D,R\_\{T\}\\;\\leq\\;GD\\sqrt\{2T\}\\;\+\\;16\\,GD\\log\(T\)\\cdot\\frac\{\\sqrt\{d\}\\cdot T\}\{S\}\\;\+\\;13\\,GD,and the number of switches satisfies𝔼​\[ST\]≤S\\mathbb\{E\}\[S\_\{T\}\]\\leq Stogether with the high\-probability bound

Pr⁡\[ST≥3​S\]≤e−S\.\\Pr\\\!\\bigl\[S\_\{T\}\\geq 3S\\bigr\]\\;\\leq\\;e^\{\-S\}\.

#### Polynomial\-time implementation\.

[Algorithm˜3](https://arxiv.org/html/2607.08012#alg3)requires sampling from the strongly log\-concave densityμt\+1​\(x\)∝exp⁡\(−β​∑τ≤tgτ​\(x\)−λ2​‖x‖2\)\\mu\_\{t\+1\}\(x\)\\propto\\exp\\bigl\(\-\\beta\\sum\_\{\\tau\\leq t\}g\_\{\\tau\}\(x\)\-\\tfrac\{\\lambda\}\{2\}\\\|x\\\|^\{2\}\\bigr\)overWW\. WhenWWadmits a polynomial\-time membership oracle—as is the case for the matroid polytope used in CR\-RAOCO—this sampling problem can be solved approximately in timepoly​\(d,T,1/ε\)\\mathrm\{poly\}\(d,T,1/\\varepsilon\)via standard log\-concave samplers such as hit\-and\-run\[Lovász and Vempala,[2007](https://arxiv.org/html/2607.08012#bib.bib42)\]\. The polynomial degree is higher than that of FTPRLL but remainspoly​\(MH,MA,N,T\)\\mathrm\{poly\}\(M\_\{H\},M\_\{A\},N,T\), matching the runtime claim of our centralized algorithm\.

### E\.3Tracking regret

The tracking regret framework has been studied to achieve good rewards relative to the baseline action changingpptimes during theTTrounds and is related to adaptive regretHazan and Seshadhri \[[2007](https://arxiv.org/html/2607.08012#bib.bib27)\]\.

Herbster and Warmuth \[[1998](https://arxiv.org/html/2607.08012#bib.bib28)\]provide an algorithm Fixed\-Share that achievesmm\-segment tracking regret𝒪​\(T​m​\(log⁡N\+log⁡T\)​N\)\\mathcal\{O\}\\left\(\\sqrt\{Tm\(\\log N\+\\log T\)N\}\\right\)in the full information setting\.Cesa\-Bianchi et al\. \[[2012](https://arxiv.org/html/2607.08012#bib.bib8)\]show that the fixed share algorithm is equivalent to online mirror descent with a particular projection\. Theorem 4\.1 ofShalev\-Shwartz et al\. \[[2012](https://arxiv.org/html/2607.08012#bib.bib53)\]shows how online mirror descent with bandit information can be implemented without degradation of regret\. This is stated in the following Theorem byDaniely et al\. \[[2015](https://arxiv.org/html/2607.08012#bib.bib14)\]\.

###### Theorem E\.5\(Restatement of theorem byDaniely et al\. \[[2015](https://arxiv.org/html/2607.08012#bib.bib14)\]\)\.

Fixed\-Share algorithm in the bandit feedback setting achieves expectedmm\-segment tracking regret at most𝒪​\(T​m​\(log⁡N\+log⁡T\)​N\)\\mathcal\{O\}\\left\(\\sqrt\{Tm\(\\log N\+\\log T\)N\}\\right\)\.

### E\.4Minmax lower bound

The tools used to show a minmax lower bound ofΩ​\(T\)\\Omega\(\\sqrt\{T\}\)regret in the standard online learning regret minimization setting can be used to derive a similar minmax lower bound ofΩ​\(T\)\\Omega\(\\sqrt\{T\}\)for assistance regret\.

That is, we can show that for any pair of human and assistant algorithms, there is an instance of the assistance game that results in assistance regret at leastΩ​\(T\)\\Omega\(\\sqrt\{T\}\)\. The lower bound is constructed through showing limitations on distinguishing between two Bernoulli distributions with means1/2\+ε1/2\+\\varepsilonand1/2−ε1/2\-\\varepsilon\.

At a high level, we can view the general online learning problem as a special case of the assistance game with just a single action that the human can take\. The assistant’s problem in this case resembles the standard external regret minimization problem\.

###### Proposition E\.6\(Assistance regret lower bound\)\.

For every human\-assistant learning algorithms, there is an instance of the online assistance game for which assistant regret isΩ​\(T\)\\Omega\(\\sqrt\{T\}\)\.

###### Proof\.

We will show a reduction from the problem of distinguishing between two Bernoulli distributions to an assistance game\.

Theε\\varepsilon\-Bernoulli distinction problem is the problem of given a distribution that is one ofBern​\(1/2−ε\)\\mathrm\{Bern\}\(1/2\-\\varepsilon\)orBern​\(1/2\+ε\)\\mathrm\{Bern\}\(1/2\+\\varepsilon\), determining which distribution it is\.

Standard lower bounds for this problem state that the probability of success of any algorithm withTTsamples in theε\\varepsilon\-Bernoulli distinction problem, is at most1−exp⁡\(−ε2​T/2\)1\-\\exp\(\-\\varepsilon^\{2\}T/2\)\.

Now we will show that these lower bounds imply a lower bound for assistance regret by establishing an algorithmic reduction

*Algorithm for distinction from algorithm for the assistance game\.*Consider any human\-assistant algorithms for the assistance game\. We can construct an algorithm for theε\\varepsilon\-Bernoulli distinction problem in the following way\.

We can set up a assistance game with a single action for the human, where the preference space isΘ=\{0,1\}\\Theta=\\\{0,1\\\}\. The assistant’s action set is𝒜=\{0,1\}\\mathcal\{A\}=\\\{0,1\\\}, and the agents receive a reward of 1 if the assistant correctly predicts the human’s preference, and a reward of 0 otherwise\. Preferences are drawn at the start of the game by nature according to the fixed distributionDDwhich can be eitherBern​\(1/2−ε\)\\mathrm\{Bern\}\(1/2\-\\varepsilon\)orBern​\(1/2\+ε\)\\mathrm\{Bern\}\(1/2\+\\varepsilon\)\.

If the assistant predicts the preference to be11more than1/21/2of the time, we conclude that the distribution isBern​\(1/2\+ε\)\\mathrm\{Bern\}\(1/2\+\\varepsilon\)and otherwise, we conclude the distribution isBern​\(1/2−ε\)\\mathrm\{Bern\}\(1/2\-\\varepsilon\)\.

Let us analyze the probability of success of this approach and relate it to the assistance regret\.

Let the assistant games induced by state generating distributionsBern​\(1/2−ε\)\\mathrm\{Bern\}\(1/2\-\\varepsilon\),Bern​\(1/2\+ε\)\\mathrm\{Bern\}\(1/2\+\\varepsilon\)beGεG\_\{\\varepsilon\},Gε′G^\{\\prime\}\_\{\\varepsilon\}respectively\. For a human\-assistant learning algorithm, letC1​\(T\)C\_\{1\}\(T\)be a random variable denoting the number of times the assistant predicts the state to be 1 inTTrounds\. For any assistant learning algorithmπ\\pi, we can write the assistance regret under the gamesGε,Gε′G\_\{\\varepsilon\},G^\{\\prime\}\_\{\\varepsilon\}asRT​\(π,Gε\)R\_\{T\}\(\\pi,G\_\{\\varepsilon\}\)andRT​\(π,Gε′\)R\_\{T\}\(\\pi,G^\{\\prime\}\_\{\\varepsilon\}\)respectively\.

We can bound both regrets in terms of the number of times the assistant predicts the preference 1 in the following way\. In gameGεG\_\{\\varepsilon\}\(state distributionBern​\(1/2−ε\)\\mathrm\{Bern\}\(1/2\-\\varepsilon\)\), the optimal fixed assistant policy is to always predict0, giving expected rewardT​\(1/2\+ε\)T\(1/2\+\\varepsilon\), while the algorithm’s expected reward isT​\(1/2\+ε\)−2​ε​𝔼​\[C1​\(T\)\]T\(1/2\+\\varepsilon\)\-2\\varepsilon\\,\\mathbb\{E\}\[C\_\{1\}\(T\)\]\(sinceaA\(t\)⟂θ\(t\)a\_\{A\}^\{\(t\)\}\\perp\\theta^\{\(t\)\}given the history\)\. Markov’s inequality on the non\-negative variableC1​\(T\)C\_\{1\}\(T\)then gives

RT​\(π,Gε\)≥2​ε​𝔼​\[C1​\(T\)\]≥T​ε⋅ℙDε​\(C1​\(T\)\>T/2\),R\_\{T\}\(\\pi,G\_\{\\varepsilon\}\)\\;\\geq\\;2\\varepsilon\\,\\mathbb\{E\}\[C\_\{1\}\(T\)\]\\;\\geq\\;T\\varepsilon\\cdot\\mathbb\{P\}\_\{D\_\{\\varepsilon\}\}\(C\_\{1\}\(T\)\>T/2\),and symmetrically \(with optimal policy “predict11always” and Markov onT−C1​\(T\)T\-C\_\{1\}\(T\)\),

RT​\(π,Gε′\)≥T​ε⋅ℙDε′​\(C1​\(T\)≤T/2\)\.R\_\{T\}\(\\pi,G^\{\\prime\}\_\{\\varepsilon\}\)\\;\\geq\\;T\\varepsilon\\cdot\\mathbb\{P\}\_\{D^\{\\prime\}\_\{\\varepsilon\}\}\(C\_\{1\}\(T\)\\leq T/2\)\.The events\{C1​\(T\)\>T/2\}\\\{C\_\{1\}\(T\)\>T/2\\\}underDεD\_\{\\varepsilon\}and\{C1​\(T\)≤T/2\}\\\{C\_\{1\}\(T\)\\leq T/2\\\}underDε′D^\{\\prime\}\_\{\\varepsilon\}are exactly the events that our test guesses incorrectly, so their sum is the total failure probability of the distinction test\. Adding the two regret bounds,

RT​\(π,Gε\)\+RT​\(π,Gε′\)\\displaystyle R\_\{T\}\(\\pi,G\_\{\\varepsilon\}\)\+R\_\{T\}\(\\pi,G^\{\\prime\}\_\{\\varepsilon\}\)≥T​ε⋅\[ℙDε​\(C1​\(T\)\>T/2\)\+ℙDε′​\(C1​\(T\)≤T/2\)\]\\displaystyle\\geq T\\varepsilon\\cdot\\bigl\[\\mathbb\{P\}\_\{D\_\{\\varepsilon\}\}\(C\_\{1\}\(T\)\>T/2\)\+\\mathbb\{P\}\_\{D^\{\\prime\}\_\{\\varepsilon\}\}\(C\_\{1\}\(T\)\\leq T/2\)\\bigr\]≥T​ε⋅Probability of failure in distinction problem\\displaystyle\\geq T\\varepsilon\\cdot\\text\{Probability of failure in distinction problem\}≥T​ε⋅exp⁡\(−ε2​T/2\),\\displaystyle\\geq T\\varepsilon\\cdot\\exp\(\-\\varepsilon^\{2\}T/2\),where the last inequality uses the standard distinction lower bound stated above \(success≤1−exp⁡\(−ε2​T/2\)\\leq 1\-\\exp\(\-\\varepsilon^\{2\}T/2\), hence failure≥exp⁡\(−ε2​T/2\)\\geq\\exp\(\-\\varepsilon^\{2\}T/2\)\)\.

Choosingε=min⁡\(1/2,1/\(4​T\)\)=1/\(2​T\)\\varepsilon=\\min\(1/2,\\sqrt\{1/\(4T\)\}\)=1/\(2\\sqrt\{T\}\)forT≥1T\\geq 1givesexp⁡\(−ε2​T/2\)=exp⁡\(−1/8\)\\exp\(\-\\varepsilon^\{2\}T/2\)=\\exp\(\-1/8\), so the sum of regrets isΩ​\(T\)\\Omega\(\\sqrt\{T\}\), and at least one ofRT​\(π,Gε\)R\_\{T\}\(\\pi,G\_\{\\varepsilon\}\),RT​\(π,Gε′\)R\_\{T\}\(\\pi,G^\{\\prime\}\_\{\\varepsilon\}\)isΩ​\(T\)\\Omega\(\\sqrt\{T\}\), which is the lower bound of the proposition\.

∎

## Appendix FAdditional Related Work

A particular subclass of assistance games are*communication games*, which are studied in the line of work on Emergent Communication \(EC\)\[Foerster et al\.,[2016](https://arxiv.org/html/2607.08012#bib.bib18), Lazaridou et al\.,[2016](https://arxiv.org/html/2607.08012#bib.bib39), Lazaridou and Baroni,[2020](https://arxiv.org/html/2607.08012#bib.bib38)\]\. This literature studies how agents learn to communicate in Lewis signaling games when trained using standard training dynamics\. Empirical work has investigated how the choice of training parameters impacts the efficiency of communication \(e\.g\.,\[Havrylov and Titov,[2017](https://arxiv.org/html/2607.08012#bib.bib26), Kim and Oh,[2021](https://arxiv.org/html/2607.08012#bib.bib34), Ren et al\.,[2019](https://arxiv.org/html/2607.08012#bib.bib49), Chaabouni et al\.,[2022](https://arxiv.org/html/2607.08012#bib.bib9), Rita et al\.,[2020](https://arxiv.org/html/2607.08012#bib.bib50), Li and Bowling,[2019](https://arxiv.org/html/2607.08012#bib.bib41)\]\) Convergence of training dynamics have received a more theoretical treatment in works in game theory and evolutionary biology showing\[Franke,[2009b](https://arxiv.org/html/2607.08012#bib.bib20),[a](https://arxiv.org/html/2607.08012#bib.bib19), Jäger,[2007](https://arxiv.org/html/2607.08012#bib.bib31),[2012](https://arxiv.org/html/2607.08012#bib.bib32), Trapa and Nowak,[2000](https://arxiv.org/html/2607.08012#bib.bib56), Kirby,[2002](https://arxiv.org/html/2607.08012#bib.bib35), Kirby et al\.,[2014](https://arxiv.org/html/2607.08012#bib.bib36), Jacob et al\.,[2023](https://arxiv.org/html/2607.08012#bib.bib30)\], but the rates of convergence are usually not analyzed\.

Training dynamics have received a more theoretical treatment in works in game theory and evolutionary biology\[Franke,[2009b](https://arxiv.org/html/2607.08012#bib.bib20),[a](https://arxiv.org/html/2607.08012#bib.bib19), Jäger,[2007](https://arxiv.org/html/2607.08012#bib.bib31),[2012](https://arxiv.org/html/2607.08012#bib.bib32), Trapa and Nowak,[2000](https://arxiv.org/html/2607.08012#bib.bib56), Kirby,[2002](https://arxiv.org/html/2607.08012#bib.bib35), Kirby et al\.,[2014](https://arxiv.org/html/2607.08012#bib.bib36), Jacob et al\.,[2023](https://arxiv.org/html/2607.08012#bib.bib30)\]\. However, these works mostly view language formation as equilibrium computation\. There are many possible equilibria and there is no guarantee of convergence to the optimal equilibrium, which is the goal of our work\.