論文の概要: Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds
- arxiv url: http://arxiv.org/abs/2206.06810v1
- Date: Tue, 14 Jun 2022 12:58:46 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-15 14:57:49.835725
- Title: Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds
- Title（参考訳）: 変数依存回帰境界を持つ逆ロバスト多元帯域幅アルゴリズム
- Authors: Shinji Ito, Taira Tsuchiya, Junya Honda
- Abstract要約: 本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 34.37963000493442
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers the multi-armed bandit (MAB) problem and provides a new
best-of-both-worlds (BOBW) algorithm that works nearly optimally in both
stochastic and adversarial settings. In stochastic settings, some existing BOBW
algorithms achieve tight gap-dependent regret bounds of $O(\sum_{i: \Delta_i>0}
\frac{\log T}{\Delta_i})$ for suboptimality gap $\Delta_i$ of arm $i$ and time
horizon $T$. As Audibert et al. [2007] have shown, however, that the
performance can be improved in stochastic environments with low-variance arms.
In fact, they have provided a stochastic MAB algorithm with
gap-variance-dependent regret bounds of $O(\sum_{i: \Delta_i>0}
(\frac{\sigma_i^2}{\Delta_i} + 1) \log T )$ for loss variance $\sigma_i^2$ of
arm $i$. In this paper, we propose the first BOBW algorithm with
gap-variance-dependent bounds, showing that the variance information can be
used even in the possibly adversarial environment. Further, the leading
constant factor in our gap-variance dependent bound is only (almost) twice the
value for the lower bound. Additionally, the proposed algorithm enjoys multiple
data-dependent regret bounds in adversarial settings and works well in
stochastic settings with adversarial corruptions. The proposed algorithm is
based on the follow-the-regularized-leader method and employs adaptive learning
rates that depend on the empirical prediction error of the loss, which leads to
gap-variance-dependent regret bounds reflecting the variance of the arms.
- Abstract（参考訳）: 本稿では,マルチアーム・バンディット(MAB)問題について考察し,確率的・対角的双方でほぼ最適に機能するBOBWアルゴリズムを提案する。
確率的設定では、既存のBOBWアルゴリズムは、$O(\sum_{i: \Delta_i>0} \frac{\log T}{\Delta_i})$ for suboptimality gap $\Delta_i$ of arm $i$ と time horizon $T$ の厳密なギャップ依存後悔境界を達成する。
audibert et alのように。
しかし,[2007]では, 低分散アームを用いた確率環境において, 性能が向上できることが示されている。
実際、彼らは、損失分散のために$O(\sum_{i: \Delta_i>0} (\frac{\sigma_i^2}{\Delta_i} + 1) \log T)$のギャップ分散依存的後悔境界を持つ確率MABアルゴリズムを提供した。
本稿では,差分依存境界を持つ最初のBOBWアルゴリズムを提案する。
さらに、ギャップ分散依存境界のリード定数は、下限の(ほぼ)2倍である。
さらに, 提案アルゴリズムは, 複数のデータ依存的後悔境界を, 対向的な設定で良好に動作させる。
提案アルゴリズムは、従順化リーダ法に基づいて、損失の経験的予測誤差に依存する適応学習率を用いて、腕の分散を反映したギャップ分散依存的後悔境界を導出する。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Towards Efficient and Optimal Covariance-Adaptive Algorithms for Combinatorial Semi-Bandits [12.674929126684528]
プレイヤーが$d$ベースアイテムを含むセットのパワーセットから$P$アクションの中から選択する半帯域の問題に対処する。
提案手法は半帯域フィードバックを効果的に活用し,帯域フィードバックアプローチより優れていることを示す。
論文 参考訳（メタデータ） (2024-02-23T08:07:54Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [45.305256056479045]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Best-of-Three-Worlds Linear Bandit Algorithm with Variance-Adaptive
Regret Bounds [27.92755687977196]
本稿では,2つの階層の環境に適応する線形帯域幅アルゴリズムを提案する。
高いレベルでは、提案アルゴリズムは様々な種類の環境に適応する。
提案アルゴリズムは、最適動作に対する累積損失のすべてに依存する、データ依存の後悔境界を有する。
論文 参考訳（メタデータ） (2023-02-24T00:02:24Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Sharp Variance-Dependent Bounds in Reinforcement Learning: Best of Both
Worlds in Stochastic and Deterministic Environments [48.96971760679639]
マルコフ決定過程(MDP)の分散依存的後悔境界について検討する。
環境の微細な分散特性を特徴付けるための2つの新しい環境規範を提案する。
モデルに基づく手法では、MVPアルゴリズムの変種を設計する。
特に、この境界は極小かつ決定論的 MDP に対して同時に最適である。
論文 参考訳（メタデータ） (2023-01-31T06:54:06Z) - Variance-Aware Sparse Linear Bandits [64.70681598741417]
余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
論文 参考訳（メタデータ） (2022-05-26T15:55:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。