論文の概要: Efficient learning by implicit exploration in bandit problems with side observations

• arxiv url: http://arxiv.org/abs/2604.24555v1
• Date: Mon, 27 Apr 2026 14:45:39 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-28 17:12:08.09669
• Title: Efficient learning by implicit exploration in bandit problems with side observations
• Title（参考訳）: サイドオブザーバを用いた帯域問題における暗黙探索による効率的な学習
• Authors: Tomas Kocak, Gergely Neu, Michal Valko, Remi Munos,
• Abstract要約: 本研究では,学習者に伝達される情報が,全情報と盗聴フィードバックの間にある状況を把握する部分的可観測性モデルに基づくオンライン学習問題を考察する。 本稿では,観測システムを知ることなく,ほぼ最適の後悔の保証を享受するアルゴリズムを提案する。 また,学習者のフィードバックが半帯域と完全フィードバックの間にあるオンライン最適化問題をモデル化する部分的情報設定も定義する。
• 参考スコア（独自算出の注目度）: 21.943714947100414
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider online learning problems under a partial observability model capturing situations where the information conveyed to the learner is between full information and bandit feedback. In the simplest variant, we assume that in addition to its own loss, the learner also gets to observe losses of some other actions. The revealed losses depend on the learner's action and a directed observation system chosen by the environment. For this setting, we propose the first algorithm that enjoys near-optimal regret guarantees without having to know the observation system before selecting its actions. Along similar lines, we also define a new partial information setting that models online combinatorial optimization problems where the feedback received by the learner is between semi-bandit and full feedback. As the predictions of our first algorithm cannot be always computed efficiently in this setting, we propose another algorithm with similar properties and with the benefit of always being computationally efficient, at the price of a slightly more complicated tuning mechanism. Both algorithms rely on a novel exploration strategy called implicit exploration, which is shown to be more efficient both computationally and information-theoretically than previously studied exploration strategies for the problem.
• Abstract（参考訳）: 本研究では,学習者に伝達される情報が,全情報と盗聴フィードバックの間にある状況を把握する部分的可観測性モデルに基づくオンライン学習問題を考察する。 最も単純な変種では、学習者は自身の損失に加えて、他の行動の損失も観察できると仮定する。 得られた損失は学習者の行動と環境が選択した観察システムに依存する。 そこで本研究では,その動作を選択する前に観測システムを知ることなく,ほぼ最適の後悔の保証を享受するアルゴリズムを提案する。 また,学習者のフィードバックが半帯域と完全フィードバックの間にあるオンライン組合せ最適化問題をモデル化する部分的情報設定も定義する。 この設定では、最初のアルゴリズムの予測が常に効率的に計算できないため、同様の特性を持つ別のアルゴリズムを提案し、より複雑なチューニング機構の価格で、常に計算効率が良いという利点がある。 どちらのアルゴリズムも暗黙の探索と呼ばれる新しい探索戦略に依存しており、この問題に対する従来研究されていた探索戦略よりも計算と情報理論の両方が効率的であることが示されている。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Representation Learning with Multi-Step Inverse Kinematics: An Efficient and Optimal Approach to Rich-Observation RL [106.82295532402335]
  既存の強化学習アルゴリズムは、計算的難易度、強い統計的仮定、最適なサンプルの複雑さに悩まされている。 所望の精度レベルに対して、レート最適サンプル複雑性を実現するための、最初の計算効率の良いアルゴリズムを提供する。 我々のアルゴリズムMusIKは、多段階の逆運動学に基づく表現学習と体系的な探索を組み合わせる。
  論文  参考訳（メタデータ） (2023-04-12T14:51:47Z)
• Deep Active Ensemble Sampling For Image Classification [8.31483061185317]
  アクティブラーニングフレームワークは、最も有益なデータポイントのラベル付けを積極的に要求することで、データアノテーションのコストを削減することを目的としている。 提案手法には、不確実性に基づく手法、幾何学的手法、不確実性に基づく手法と幾何学的手法の暗黙の組み合わせなどがある。 本稿では, サンプル選択戦略における効率的な探索・探索トレードオフを実現するために, 不確実性に基づくフレームワークと幾何学的フレームワークの両方の最近の進歩を革新的に統合する。 本フレームワークは,(1)正確な後続推定,(2)計算オーバーヘッドと高い精度のトレードオフの2つの利点を提供する。
  論文  参考訳（メタデータ） (2022-10-11T20:20:20Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• The Information Geometry of Unsupervised Reinforcement Learning [133.20816939521941]
  教師なしスキル発見(英語: Unsupervised skill discovery)とは、報酬関数にアクセスせずに一連のポリシーを学ぶアルゴリズムのクラスである。 教師なしのスキル発見アルゴリズムは、あらゆる報酬関数に最適なスキルを学習しないことを示す。
  論文  参考訳（メタデータ） (2021-10-06T13:08:36Z)
• Experimental Design for Regret Minimization in Linear Bandits [19.8309784360219]
  オンライン・リニア・バンドレットにおける後悔を最小限に抑える設計に基づく新しいアルゴリズムを提案する。 我々は、現在最先端の有限時間後悔保証を提供し、このアルゴリズムが帯域幅と半帯域幅の両方のフィードバックシステムに適用可能であることを示す。
  論文  参考訳（メタデータ） (2020-11-01T17:59:19Z)
• Learning to Actively Learn: A Robust Approach [14.46867518436922]
  本研究では,アクティブラーニングや純粋探索型マルチアームバンディットといった適応データ収集タスクのアルゴリズム設計手法を提案する。 我々の適応アルゴリズムは、情報理論の下界から導かれる問題の同値クラスに対する逆学習によって学習される。 我々は,訓練手順の安定性と有効性を正当化するための合成実験を行い,実データから導出される課題について評価する。
  論文  参考訳（メタデータ） (2020-10-29T06:48:22Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  強化学習アルゴリズムは、いくつかのルールの1つに従ってエージェントのパラメータを更新する。 本稿では,更新ルール全体を検出するメタラーニング手法を提案する。 これには、一連の環境と対話することで、"何を予測するか"(例えば、値関数)と"どのように学習するか"の両方が含まれている。
  論文  参考訳（メタデータ） (2020-07-17T07:38:39Z)
• Meta-learning with Stochastic Linear Bandits [120.43000970418939]
  我々は、よく知られたOFULアルゴリズムの正規化バージョンを実装するバンディットアルゴリズムのクラスを考える。 我々は,タスク数の増加とタスク分散の分散が小さくなると,タスクを個別に学習する上で,我々の戦略が大きな優位性を持つことを理論的および実験的に示す。
  論文  参考訳（メタデータ） (2020-05-18T08:41:39Z)

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

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