論文の概要: Efficient contextual partial monitoring with general function approximation

• arxiv url: http://arxiv.org/abs/2610.19804v1
• Date: Wed, 14 Oct 2026 08:48:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-15 21:06:16.041782
• Title: Efficient contextual partial monitoring with general function approximation
• Title（参考訳）: 一般関数近似を用いた効率的な文脈部分モニタリング
• Abstract要約: 部分的フィードバックによる学習のパラダイムである側面情報を用いた有限部分監視(PM)ゲームについて検討する。 我々は,E2D.PMSideの設計にE2Dメタアルゴリズムを用いた。 我々は、OE2D.PMSideと呼ばれるE2D.PMSideの変種をオフライン回帰オラクルと組み合わせることで、最適な後悔を伴う効率的なアルゴリズムを与えることを示した。
• 参考スコア（独自算出の注目度）: 27.931910075087632
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study finite stochastic partial monitoring (PM) games with side information, a paradigm of sequential learning with partial feedback. On each round $t \in [T]$, both player and environment observe a context and player chooses an action and environment simultaneously chooses an outcome. The player neither observes the outcome nor the loss; instead, they only observe a feedback symbol which is partially informative about the outcome. We utilize the Estimation-to-Decisions (E2D) meta-algorithm of Foster et al.(2021) to design E2D.PMSide, a computationally efficient framework for contextual partial monitoring, which uses an online regression oracle to efficiently estimate the outcome distributions based on historical (context, action, feedback symbol) tuples. Since the exploration rule given by the original E2D algorithm is intractable to compute, we propose two computationally efficient exploration rules that achieve optimal regret orders in $T$: in the globally observable setting, our exploration rule is based on $ε$-greedy, while in the locally observable setting, our exploration rule uses inverse gap weighting (Foster & Rakhlin, 2020), which was previously only known to be effective in the bandit setting. We show that a variant of E2D.PMSide named OE2D.PMSide can be combined with offline regression oracles to give an efficient algorithm with optimal regret when the contexts are drawn independently from a fixed distribution. We evaluate our algorithm on a synthetic label-efficient prediction game and an LLM routing task, in which a learner decides from prompt, uncertainty, and internal state features whether to escalate a query from a weak model to a strong one. We show that our method has superior performance to prior approaches.
• Abstract（参考訳）: 部分的フィードバックを伴う逐次学習のパラダイムである側面情報を用いた有限確率部分監視(PM)ゲームについて検討した。 各ラウンド$t \in [T]$では、プレイヤーと環境の両方がコンテキストを観察し、プレイヤーはアクションを選択し、環境は同時に結果を選択する。 プレイヤーは結果も損失も観察せず、結果について部分的に情報を与えるフィードバックシンボルのみを観察する。 我々は,Foster et al (2021) のメタアルゴリズムであるE2D-to-Decisions (E2D) を用いて,歴史的(コンテキスト,アクション,フィードバックのシンボル) タプルに基づいて結果分布を効率的に推定するオンライン回帰オラクルを用いて,文脈的部分的監視のための計算効率の高いフレームワーク E2D.PMSide を設計する。 元のE2Dアルゴリズムで与えられた探索規則は計算に難航するので、2つの計算効率の良い探索規則をT$で提案する: グローバルな観測可能な設定では、探索規則はε$-greedyに基づいており、局所的な観測可能な設定では、我々の探索規則は逆ギャップ重み付け(Foster & Rakhlin, 2020)を用いる。 OE2D.PMSide と呼ばれる E2D.PMSide の変種をオフライン回帰オラクルと組み合わせることで、コンテキストが固定分布から独立して引き出されるとき、最適な後悔を伴う効率的なアルゴリズムを実現できることを示す。 提案アルゴリズムは,学習者が探索,不確実性,内部状態から,弱いモデルから強いモデルへクエリをエスカレートするか否かを判断する合成ラベル効率予測ゲームとLLMルーティングタスクで評価する。 本手法は従来の手法よりも優れた性能を示す。

関連論文リスト

• Taming the Monster Every Context: Complexity Measure and Unified Framework for Offline-Oracle Efficient Contextual Bandits [17.2911371867411]
  一般報酬関数近似による文脈的帯域学習をオフライン回帰に還元するアルゴリズムフレームワークOE2Dを提案する。 このフレームワークは、$O(log(T))$のオフライン回帰オラクルを$T$のラウンドで呼び出す大きなアクション空間を持つコンテキスト的バンディットに対して、ほぼ最適に後悔することができる。 我々の後悔分析の中心は、Decision-Offline Estimation Coefficient (DOEC)と呼ばれる新しい複雑さ尺度であり、これはコンテキストごとの有界エルダー次元とスムーズな後悔設定で表される。
  論文  参考訳（メタデータ） (2026-02-10T06:45:57Z)
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback [61.49239204705301]
  本研究では,有限水平マルコフ決定過程(MDP)におけるオンライン学習について,包括的包括的包括的フィードバックモデルを用いて検討する。 本研究は, オンライン最短経路問題の近年の進展に触発された, 占領対策, 自己拘束技術, 新たな損失推定器の組合せに依拠する。
  論文  参考訳（メタデータ） (2025-10-20T02:28:08Z)
• Two-Player Zero-Sum Games with Bandit Feedback [6.66618805642802]
  本研究では,行プレーヤが敵列プレーヤに対する報酬を最大化することを目的とした2プレイヤーゼロサムゲームについて検討する。 本研究では,Explore-Then-Commitフレームワークに基づく3つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-06-17T13:46:32Z)
• Nearly Optimal Algorithms for Contextual Dueling Bandits from Adversarial Feedback [58.66941279460248]
  人からのフィードバックから学ぶことは、大言語モデル(LLM)のような生成モデルを調整する上で重要な役割を果たす 本稿では,このドメイン内のモデルについて考察する。-文脈的デュエルバンディット(contextual dueling bandits)と,正の選好ラベルを相手によって反転させることができる対向フィードバック(reversarial feedback)について考察する。 本稿では,不確実性重み付き最大推定に基づく頑健なコンテキストデュエルバンドイット(RCDB)を提案する。
  論文  参考訳（メタデータ） (2024-04-16T17:59:55Z)
• Exploration by Optimization with Hybrid Regularizers: Logarithmic Regret with Adversarial Robustness in Partial Monitoring [41.20252349191698]
  部分的な監視は、限られたフィードバックを伴うオンライン意思決定問題の一般的なフレームワークである。 ハイブリッド正規化器を用いたExOの新しいフレームワークと解析法を提案する。 特に、$O(sum_a neq a*)$で、$k$、$m$、$T$はアクション、観察、ラウンドの数である。
  論文  参考訳（メタデータ） (2024-02-13T09:34:22Z)
• Contextual Decision-Making with Knapsacks Beyond the Worst Case [5.65888994172721]
  資源制約を伴う動的意思決定シナリオの枠組みについて検討する。 このフレームワークでは、エージェントがランダムな要求を観察すると、各ラウンドでアクションを選択する。 我々のアルゴリズムは最悪の場合であっても、ほぼ最適の$widetildeO(sqrtT)$ regretを維持していることを証明している。
  論文  参考訳（メタデータ） (2022-11-25T08:21:50Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  アクティブラーニングフレームワークは、最も有益なデータポイントのラベル付けを積極的に要求することで、データアノテーションのコストを削減することを目的としている。 提案手法には、不確実性に基づく手法、幾何学的手法、不確実性に基づく手法と幾何学的手法の暗黙の組み合わせなどがある。 本稿では, サンプル選択戦略における効率的な探索・探索トレードオフを実現するために, 不確実性に基づくフレームワークと幾何学的フレームワークの両方の最近の進歩を革新的に統合する。 本フレームワークは,(1)正確な後続推定,(2)計算オーバーヘッドと高い精度のトレードオフの2つの利点を提供する。
  論文  参考訳（メタデータ） (2022-10-11T20:20:20Z)
• Provably Efficient Offline Reinforcement Learning with Trajectory-Wise Reward [66.81579829897392]
  我々はPessimistic vAlue iteRaTionとrEward Decomposition (PARTED)という新しいオフライン強化学習アルゴリズムを提案する。 PartEDは、最小2乗ベースの報酬再分配を通じて、ステップごとのプロキシ報酬に軌道を分解し、学習したプロキシ報酬に基づいて悲観的な値を実行する。 私たちの知る限りでは、PartEDは、トラジェクティブな報酬を持つ一般のMDPにおいて、証明可能な効率のよい最初のオフラインRLアルゴリズムである。
  論文  参考訳（メタデータ） (2022-06-13T19:11:22Z)
• Anti-Concentrated Confidence Bonuses for Scalable Exploration [57.91943847134011]
  固有の報酬は、探検と探検のトレードオフを扱う上で中心的な役割を果たす。 楕円ボーナスを効率的に近似するためのエンファンティ集中型信頼境界を導入する。 我々は,Atariベンチマーク上での現代固有の報酬と競合する,深層強化学習のための実用的な変種を開発する。
  論文  参考訳（メタデータ） (2021-10-21T15:25:15Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。