論文の概要: Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses

• arxiv url: http://arxiv.org/abs/2602.07418v1
• Date: Sat, 07 Feb 2026 07:32:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-10 20:26:24.612969
• Title: Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses
• Title（参考訳）: 決定論的損失を伴う帯域における最適静的および動的レギュレットの同時獲得
• Authors: Jian Qian, Chen-Yu Wei,
• Abstract要約: 敵の多武装の包帯では、静的な後悔とダイナミックな後悔という2つのパフォーマンス尺度が一般的である。 最適なアルゴリズムは各測度ごとに知られているが、両方の最適境界を同時に達成する既知のアルゴリズムは存在しない。 本稿では,不愉快な相手に対して,最適な静的および動的後悔を同時に達成するアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 24.77915694853164
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In adversarial multi-armed bandits, two performance measures are commonly used: static regret, which compares the learner to the best fixed arm, and dynamic regret, which compares it to the best sequence of arms. While optimal algorithms are known for each measure individually, there is no known algorithm achieving optimal bounds for both simultaneously. Marinov and Zimmert [2021] first showed that such simultaneous optimality is impossible against an adaptive adversary. Our work takes a first step to demonstrate its possibility against an oblivious adversary when losses are deterministic. First, we extend the impossibility result of Marinov and Zimmert [2021] to the case of deterministic losses. Then, we present an algorithm achieving optimal static and dynamic regret simultaneously against an oblivious adversary. Together, they reveal a fundamental separation between adaptive and oblivious adversaries when multiple regret benchmarks are considered simultaneously. It also provides new insight into the long open problem of simultaneously achieving optimal regret against switching benchmarks of different numbers of switches. Our algorithm uses negative static regret to compensate for the exploration overhead incurred when controlling dynamic regret, and leverages Blackwell approachability to jointly control both regrets. This yields a new model selection procedure for bandits that may be of independent interest.
• Abstract（参考訳）: 敵の多腕包帯では、静的後悔(スタティック後悔)と動的後悔(ダイナミック後悔)の2つのパフォーマンス尺度が一般的である。 最適なアルゴリズムは各測度ごとに知られているが、両方の最適境界を同時に達成する既知のアルゴリズムは存在しない。 Marinov と Zimmert [2021] は、適応的敵に対してそのような同時最適性は不可能であることを示した。 私たちの研究は、損失が決定論的である場合、不利な敵に対してその可能性を示す第一歩を踏み出します。 まず、Marinov と Zimmert [2021] の不合理性の結果を決定論的損失の場合にまで拡張する。 そこで我々は,不愉快な相手に対して,最適な静的および動的後悔を同時に達成するアルゴリズムを提案する。 同時に、複数の後悔のベンチマークが同時に検討されるとき、適応性と難解な敵の根本的な分離を明らかにする。 また、異なる数のスイッチのベンチマークを切り替えることに対して最適な後悔を同時に達成する、長いオープンな問題に対する新たな洞察を提供する。 我々のアルゴリズムは、動的後悔を制御する際に生じる探索オーバーヘッドを補償するために負の静的後悔を使い、ブラックウェルのアプローチ性を利用して両方の後悔を共同で制御する。 これにより、独立した関心を持つ可能性のあるバンディットの新しいモデル選択手順が得られる。

関連論文リスト

• Best Arm Identification with Minimal Regret [55.831935724659175]
  最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。 エージェントの目標は、所定の信頼度で最高の腕を特定することである。 二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
  論文  参考訳（メタデータ） (2024-09-27T16:46:02Z)
• Multi-Armed Bandits with Abstention [62.749500564313834]
  本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。 この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
  論文  参考訳（メタデータ） (2024-02-23T06:27:12Z)
• Accelerated Rates between Stochastic and Adversarial Online Convex Optimization [6.1866042321432175]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 完全i.d.の場合、我々の後悔の限界は加速の結果から期待される速度と一致し、オンラインからバッチへの変換によって最適に加速された速度を回復する。
  論文  参考訳（メタデータ） (2023-03-06T16:41:57Z)
• Regret Minimization and Convergence to Equilibria in General-sum Markov Games [61.6869963435955]
  汎用マルコフゲームにおいて,全てのエージェントが実行した場合のサブ線形後悔保証を提供する学習アルゴリズムを初めて提示する。 我々のアルゴリズムは分散化され、計算効率が良く、エージェント間の通信は不要である。
  論文  参考訳（メタデータ） (2022-07-28T16:27:59Z)
• Between Stochastic and Adversarial Online Convex Optimization: Improved Regret Bounds via Smoothness [2.628557920905129]
  我々は,オンライン凸最適化において,対人的損失と完全対人的損失を補間する新たな後悔境界を確立する。 この目的を達成するために、損失系列に関連する2つの重要な量を導入し、累積分散と対角変動と呼ぶ。 完全な i.d. の場合、我々の境界は加速の結果から期待される速度と一致し、完全に反対の場合、ミニマックスの後悔と一致するように優雅に劣化する。
  論文  参考訳（メタデータ） (2022-02-15T16:39:33Z)
• Versatile Dueling Bandits: Best-of-both-World Analyses for Online Learning from Preferences [28.79598714109439]
  両環境および敵環境における$K$武器のデュエルバンディットの問題について検討する。 まず,マルチアームのバンディットに対して,任意の(一般的な)デュエル・バンドレットから新たなリダクションを提案する。 提案アルゴリズムは,コンドルチェット・ウィンナーベンチマークに対して最適な$O(sum_i = 1K fraclog TDelta_i)$ regret boundを達成した最初のアルゴリズムでもある。
  論文  参考訳（メタデータ） (2022-02-14T13:37:23Z)
• A closer look at temporal variability in dynamic online learning [19.468067110814808]
  この作品は、完全な情報でオンライン学習の文脈でダイナミックな後悔の設定に焦点を当てています。 損失関数の列は時間とともに大きく変化しないと仮定することにより、既存の結果と比較して改善された後悔境界を導き出すことが可能であることを示す。
  論文  参考訳（メタデータ） (2021-02-15T16:50:16Z)
• Lenient Regret for Multi-Armed Bandits [72.56064196252498]
  エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。 アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。 我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
  論文  参考訳（メタデータ） (2020-08-10T08:30:52Z)
• Bias no more: high-probability data-dependent regret bounds for adversarial bandits and MDPs [48.44657553192801]
  我々は,適応的相手に対する盗聴フィードバックを用いたオンライン学習において,高い確率的後悔境界を得るための新しいアプローチを開発した。 我々のアプローチは、対数的に均質な自己協和障壁と強化されたフリードマンの不平等の助けを借りて、単純な学習率のスケジュールの増大に依存している。
  論文  参考訳（メタデータ） (2020-06-14T22:09:27Z)

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

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