論文の概要: Provably Optimal Learning Algorithms for Assistance Games
- arxiv url: http://arxiv.org/abs/2607.08012v1
- Date: Thu, 09 Jul 2026 00:38:42 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-07-10 14:45:27.376033
- Title: Provably Optimal Learning Algorithms for Assistance Games
- Title（参考訳）: アシストゲームのための確率的最適学習アルゴリズム
- Authors: Nivasini Ananthakrishnan, Mark Bedaywi, Michael I. Jordan, Stuart Russell, Nika Haghtalab,
- Abstract要約: 我々は、繰り返しアシストゲームのための最初の証明可能な効率的な学習アルゴリズムを提供する。
情報化人間とアシスタントの両方に分散化アルゴリズムを提案する。
後悔の近似係数が1-1/eより良いことを証明した。
- 参考スコア（独自算出の注目度）: 60.843021846414956
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: This paper studies an online variant of the assistance games framework, where an informed agent and an uninformed agent repeatedly interact over $T$ timesteps 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)$-approximate assistance regret rate of $\widetilde{O}(T^{3/4})$, 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)$ 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 $\widetilde{O}(T^{1/2})$, optimal up to logarithmic factors.
- Abstract（参考訳）: 本稿では,支援ゲームフレームワークのオンライン版について検討し,インフォームドエージェントと非インフォームドエージェントが,共通の報酬関数を最適化するために,T$タイムステップで繰り返し対話する。
情報提供者(人間)は世界の潜伏状態を観察するが、情報提供者(アシスタント)は人間の行動のみを観察する。
我々は、繰り返しアシストゲームのための最初の証明可能な効率的な学習アルゴリズムを提供する。
我々は、相互作用の累積効用と、潜在状態を行動ペアにマッピングする後見における最適な共同政策のギャップという、援助後悔の概念を紹介した。
1-1/e)$-approximate aid regret rate of $\widetilde{O}(T^{3/4})$, with runtime polynomial in the size of the action and state space。
これらのアルゴリズムは汎用的であり、特にアシスタントの非regretアルゴリズムに対応している。
後悔の近似係数が1-1/eより良いことを証明した。
さらに、これらの一般的な非回帰アルゴリズムが擬分散的な設定(共有ランダム文字列を使って)に合わせることで、対数因子まで最適に$\widetilde{O}(T^{1/2})$を達成できることを示す。
関連論文リスト
- Single-Sample and Robust Online Resource Allocation [14.956072215503797]
本稿では,オンラインリソースアロケーションのための新しい指数価格アルゴリズムを提案する。
外れ値モデルと値拡張モデルにおける汚職に対して堅牢である。
アイテムの価格設定にオンライン学習アルゴリズムを使用する従来のアプローチから運用されている。
論文 参考訳（メタデータ） (2025-05-05T18:48:11Z) - Near-Optimal Online Learning for Multi-Agent Submodular Coordination: Tight Approximation and Communication Efficiency [52.60557300927007]
離散部分モジュラー問題を連続的に最適化するために,$textbfMA-OSMA$アルゴリズムを提案する。
また、一様分布を混合することによりKLの発散を効果的に活用する、プロジェクションフリーな$textbfMA-OSEA$アルゴリズムも導入する。
我々のアルゴリズムは最先端OSGアルゴリズムによって提供される$(frac11+c)$-approximationを大幅に改善する。
論文 参考訳（メタデータ） (2025-02-07T15:57:56Z) - Learning to Play Against Unknown Opponents [9.346742321348366]
本研究では,学習エージェントが非学習に制約されない場合に,最適な学習アルゴリズムを効率的に構築する方法を示す。
これらの結果は、最近開発された機械を用いて、学習アルゴリズムの分析をメニューとして知られる幾何学的対象のクラスに変換する。
論文 参考訳（メタデータ） (2024-12-24T09:05:06Z) - Provably Efficient Reinforcement Learning via Surprise Bound [66.15308700413814]
本稿では,一般値関数近似を用いた効率の良い強化学習アルゴリズムを提案する。
本アルゴリズムは, 線形設定と疎高次元線形設定の両方に適用した場合に, 合理的な後悔境界を達成できる。
論文 参考訳（メタデータ） (2023-02-22T20:21:25Z) - Improved Regret for Efficient Online Reinforcement Learning with Linear
Function Approximation [69.0695698566235]
線形関数近似による強化学習と,コスト関数の逆変化について検討した。
本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T17:26:39Z) - On the Sample Complexity of Representation Learning in Multi-task
Bandits with Global and Local structure [77.60508571062958]
マルチタスク・バンディット問題に対する最適アーム学習の複雑さについて検討した。
アームは2つのコンポーネントで構成されます。1つはタスク間で共有され(表現と呼ばれます)、もう1つはタスク固有のもの(予測器と呼ばれます)です。
サンプルの複雑さが下界に近づき、最大で$H(Glog(delta_G)+ Xlog(delta_H))$でスケールするアルゴリズムOSRL-SCを考案する。
論文 参考訳（メタデータ） (2022-11-28T08:40:12Z) - Doubly Optimal No-Regret Online Learning in Strongly Monotone Games with Bandit Feedback [29.553652241608997]
本研究では,テキストモオと強いモノトーンゲームの研究を行い,その学習方法について検討した。
我々はまず,新しい帯域学習アルゴリズムを構築し,$tildeTheta(nsqrtT)$の単一エージェント最適後悔を実現することを示す。
そこで我々は,このオープンな問題を解決し,広範にわたるバンディットゲーム理論学習に寄与した。
論文 参考訳（メタデータ） (2021-12-06T08:27:54Z) - Online Sub-Sampling for Reinforcement Learning with General Function
Approximation [111.01990889581243]
本稿では,RLアルゴリズムによって収集されたデータポイントの情報取得量を測定する,効率的なオンラインサブサンプリングフレームワークを確立する。
複雑性バウンド関数クラスを持つ値ベースのメソッドの場合、$proptooperatornamepolylog(K)$ timesに対してのみポリシーを更新する必要がある。
少なくとも$Omega(K)$倍のポリシーを更新する既存のアプローチとは対照的に、当社のアプローチはポリシーの解決における最適化コールの数を劇的に削減します。
論文 参考訳（メタデータ） (2021-06-14T07:36:25Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。