{"id":"35e72281-ea7c-46df-babb-1e0a908361b3","arxiv_id":"2607.08012","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.5,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Decentralized poly-time algorithms achieve (1-1/e)-approximate assistance regret Õ(T^{3/4}) (or Õ(√T) with shared randomness) for online assistance games, and better approximation is intractable.","lead":"This paper gives the first efficient decentralized learning algorithms for online assistance games, where a human who sees a private state and an AI assistant who only sees the human's actions must jointly maximize shared reward. The algorithms achieve near-optimal (1-1/e)-approximate assistance regret, with a matching hardness result, providing a rigorous foundation for cooperative human-AI systems under information asymmetry.","discovery_kind":"new_method","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader correctly identifies the strongest claims and the only structural limitation (oblivious nature). That limitation is proved necessary by the authors themselves and does not undermine the theorems as stated. The technical core—matroid representation, weighted-threshold structure of V_\theta, CR-RAOCO with POMER, Fixed-Share tracking, and the shared-map improvement—is standard and carefully assembled; the hardness reduction is classical. No load-bearing flaw appears that would move the verdict away from ACCEPT.","tokens_in":30982,"tokens_out":405,"duration_ms":5089,"concrete_test":"Independently re-derive the sandwich property for the value-of-assistance function V_\theta under coupled swap rounding (Proposition E.1 + Algorithm 3) and confirm that the (1-1/e) factor and the switch-preserving property (Proposition E.3) both survive; if either fails, the transfer of POMER regret/switch bounds into Proposition 6.1 collapses.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claims (Theorems 4.1–4.3) rest on a clean reduction of joint policy optimization to online maximization of weighted threshold potentials over a partition matroid (Proposition 5.4, Lemmas D.1–D.3), a stability-adaptivity decomposition (Lemma 4.4), and a standard hardness reduction from max-k-coverage (Lemma C.1). The oblivious-nature restriction is necessary (Appendix B) and is stated as such; the (1-1/e) factor is tight under poly-time constraints; and the √T rate with shared randomness is optimal up to logs (Proposition E.6). No derivation gap, circularity, or unstated assumption that would invalidate the regret or hardness statements was found.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","summary":"The paper studies an online variant of assistance games (cooperative inverse RL) in which a human who observes a latent preference sequence θ^(t) and an assistant who observes only the human’s actions interact for T rounds under a common reward. It defines α-assistance regret against the best joint policy pair in hindsight and gives the first poly(M_H, M_A, N, T)-time decentralized algorithms that achieve (1-1/e)-approximate assistance regret Õ(T^{3/4}) (Theorem 4.1). With a shared encoding from human-action sequences to assistant policies the rate improves to Õ(√T), optimal up to logs (Theorem 4.2). A matching hardness result shows that any better approximation factor is intractable unless RP=NP (Theorem 4.3). The technical core is a reduction of joint policy optimization to online maximization of weighted threshold potentials over a partition matroid (the assistance matroid), a stability–adaptivity regret decomposition (Lemma 4.4), and standard black-box tools (RAOCO, POMER, Fixed-Share).","tokens_in":31198,"tokens_out":892,"duration_ms":19110,"significance":"If the claims hold, the paper closes a long-standing open problem: the first computationally efficient, provably near-optimal learning algorithms for repeated assistance games. The reduction to online submodular maximization under matroid constraints is clean and reusable; the stability–adaptivity decomposition cleanly separates the coordination problem from the computational one; and the hardness result pins down the (1-1/e) barrier. The √T rate with shared randomness is information-theoretically tight (Proposition E.6), and the necessity of an oblivious adversary is proved rather than assumed (Appendix B). Complete proofs appear in the appendices, the algorithms are modular (any tracking-regret assistant works for the T^{3/4} result), and the discussion honestly lists the remaining open questions (dependence on action-space sizes, necessity of the shared map, richer interaction models). These are genuine strengths for a theory paper in cooperative multi-agent learning.","major_comments":[],"minor_comments":[{"comment":"Section 7 (Limitations) notes that the optimal √T rate relies on a pre-shared encoding φ. A short remark on whether a weaker form of synchronization (e.g., a short public random seed plus a fixed encoding of Π_A) would suffice would help readers assess practicality.","section":null},{"comment":"In the proof of Proposition 6.1 / Appendix D.6 the Lipschitz constant of the concave relaxation is taken w.r.t. ℓ_1 and then converted to ℓ_2; a one-line reminder that G ≤ √(M_A M_H) would make the substitution into Theorem E.4 completely self-contained.","section":null},{"comment":"Notation for the human policy sometimes appears as π_H and sometimes as the best-response map π*_H(θ); a consistent convention in Section 5 would improve readability.","section":null},{"comment":"Appendix B (adaptive nature) is important for justifying the model; a forward pointer from the main-text model section would help readers who skip the appendix.","section":null},{"comment":"A few minor typos appear (e.g., “asssistant” in the policy-space paragraph of Section 5.1; “the the assistant” in Lemma 4.4). A light copy-edit pass would clean them up.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is technically solid and the contribution is clear. I see no reason to delay acceptance for the minor presentation points listed above; they can be handled in production. The paper is a good fit for a theory-oriented ML or multi-agent learning venue."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the first set of efficient, decentralized algorithms that actually deliver sublinear assistance regret for the online version of assistance games (CIRL). They get (1-1/e)-approx Õ(T^{3/4}) in poly time, improve to Õ(√T) with a shared random map, and prove you cannot beat 1-1/e efficiently unless RP=NP.\n\nWhat is new is the formulation itself (assistance regret against the best joint policy pair in hindsight), the reduction of joint policy optimization to online maximization of weighted threshold potentials over a partition matroid (the “assistance matroid” and value-of-assistance function V_θ), and the stability-adaptivity decomposition that lets them wrap any low-switch centralized OCO algorithm with any low-tracking-regret assistant. They instantiate it carefully with RAOCO + coupled rounding + POMER for the human side and Fixed-Share copies for the assistant. The hardness reduction from max-k-coverage is standard but cleanly executed, and Appendix B correctly shows that an adaptive nature forces linear regret even on simple signaling games, so the oblivious assumption is necessary rather than a hidden weakness.\n\nThe math looks solid: the structural lemmas (V_θ is 1-Lipschitz weighted threshold, matroid is partition of rank M_H) check out, the regret transfer is direct from Salem et al., and the switch bound via coupled randomness is the right technical fix. Citation pattern is appropriate; they engage the CIRL literature, online submodular work, and tracking-regret tools without padding.\n\nSoft spots are minor and acknowledged: the M_H/M_A dependence may not be tight, the optimal √T rate needs a pre-shared encoding, and there are no experiments (pure theory). None of these undercut the claims.\n\nThis is for people working on multi-agent online learning, human-AI collaboration theory, or alignment foundations who want the first non-asymptotic guarantees in this model. It deserves a serious referee; I would accept it for peer review and would bring it to reading group.","headline":"First poly-time algorithms with sublinear (1-1/e)-assistance regret for online CIRL/assistance games, via a clean submodular reduction and matching hardness.","tokens_in":31765,"tokens_out":527,"would_cite":true,"duration_ms":10768,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"Decentralized algorithms learn near-optimal human–assistant coordination under information asymmetry at rates Õ(T^{3/4}) and Õ(√T), and (1−1/e) is the best efficient approximation factor.","keywords":["assistance games","online learning","assistance regret","submodular maximization","tracking regret","human-AI coordination","cooperative inverse reinforcement learning"],"falsifier":"An efficient algorithm that achieves sublinear α-approximate assistance regret for any constant α > 1−1/e on the offline max-coverage reduction used in the hardness proof, or a matching lower-bound instance showing that the √T rate is impossible without a shared encoding.","tokens_in":31903,"feed_emoji":"🤖","tokens_out":641,"duration_ms":6775,"temperature":0.7,"pith_summary":"When a human who sees private preferences must repeatedly interact with an AI assistant that only sees the human’s actions, the two agents share a reward but lack a common language or joint planner. The paper shows that this online assistance game can still be solved efficiently: decentralized learning rules for both parties achieve (1−1/e)-approximate assistance regret that vanishes as T^{3/4}, and with a one-time shared encoding of policies the rate improves to the information-theoretically optimal √T. The same approximation factor is tight; nothing better is possible for polynomial-time algorithms unless RP=NP. The construction works by reducing joint policy search to online submodular maximization over a partition matroid and then decomposing the resulting regret into a stable centralized component plus an adaptive assistant component. A sympathetic reader cares because this supplies the first formal guarantee that assistive AI can learn to act on a human’s behalf without pre-specified communication protocols or centralized control.","feed_headline":"AI assistants learn to help without a shared language","feed_subtitle":"First poly-time algorithms give near-optimal (1-1/e) regret rates for repeated human-assistant play","key_machinery":"Assistance regret together with its stable–adaptive decomposition: the gap to the best joint policy in hindsight is bounded by the external regret of a centralized submodular maximizer, the number of policy switches that maximizer makes, and the assistant’s tracking regret against that moving target.","core_discovery":"There exist polynomial-time decentralized algorithms for the human and the assistant that achieve (1−1/e)-approximate assistance regret of order T^{3/4}; with a shared map from sequences of human actions to assistant policies the same approximation improves to order √T (optimal up to logs); and no efficient algorithm can beat the (1−1/e) factor unless RP=NP.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["First poly-time algos for (1-1/e) assistance regret Õ(T^{3/4})","Decentralized human-assistant learners hit near-optimal regret rates","Shared randomness yields optimal Õ(√T) assistance regret","No efficient method beats (1-1/e) factor unless RP=NP","Provable poly-time learning in repeated assistance games"],"cache_read_input_tokens":16512,"weakest_assumption_plain":"The sequence of private preferences is fixed before the game starts and cannot react to what the human or assistant actually does.","fun_headline_variants_meta":{"raw":{"variants":["First poly-time algos for (1-1/e) assistance regret Õ(T^{3/4})","Decentralized human-assistant learners hit near-optimal regret rates","Shared randomness yields optimal Õ(√T) assistance regret","No efficient method beats (1-1/e) factor unless RP=NP","Provable poly-time learning in repeated assistance games"]},"model":"grok-4.5","effort":"low","cost_usd":0.003818,"raw_usage":{"total_tokens":1189,"prompt_tokens":781,"num_sources_used":0,"completion_tokens":88,"cost_in_usd_ticks":38180000,"prompt_tokens_details":{"text_tokens":781,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":320,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":781,"tokens_out":88,"duration_ms":3932,"temperature":1.0,"reasoning_tokens":320,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-10T13:45:08.190847+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"An efficient algorithm that achieves sublinear α-approximate assistance regret for any constant α > 1−1/e on the offline max-coverage reduction used in the hardness proof, or a matching lower-bound instance showing that the √T rate is impossible without a shared encoding.","supporting_citations":[],"review_version":1}