論文の概要: From Theory to Practice with RAVEN-UCB: Addressing Non-Stationarity in Multi-Armed Bandits through Variance Adaptation
- arxiv url: http://arxiv.org/abs/2506.02933v1
- Date: Tue, 03 Jun 2025 14:35:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-06-04 21:47:35.793779
- Title: From Theory to Practice with RAVEN-UCB: Addressing Non-Stationarity in Multi-Armed Bandits through Variance Adaptation
- Title（参考訳）: RAVEN-UCBによる理論から実践へ:可変適応によるマルチアーマッドバンドの非定常性に対処する
- Authors: Junyi Fang, Yuxun Chen, Yuxin Chen, Chen Zhang,
- Abstract要約: RAVEN-UCBは,分散適応による理論リガーと実用効率を組み合わせた新しいアルゴリズムである。
これは UCB1 と UCB-V よりも厳密な後悔境界を達成し、ギャップ依存の残差は$K sigma_max2 log T / Delta$ であり、ギャップ非依存の残差は$sqrtK T log T$ である。
- 参考スコア（独自算出の注目度）: 13.490692458295301
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: The Multi-Armed Bandit (MAB) problem is challenging in non-stationary environments where reward distributions evolve dynamically. We introduce RAVEN-UCB, a novel algorithm that combines theoretical rigor with practical efficiency via variance-aware adaptation. It achieves tighter regret bounds than UCB1 and UCB-V, with gap-dependent regret of order $K \sigma_{\max}^2 \log T / \Delta$ and gap-independent regret of order $\sqrt{K T \log T}$. RAVEN-UCB incorporates three innovations: (1) variance-driven exploration using $\sqrt{\hat{\sigma}_k^2 / (N_k + 1)}$ in confidence bounds, (2) adaptive control via $\alpha_t = \alpha_0 / \log(t + \epsilon)$, and (3) constant-time recursive updates for efficiency. Experiments across non-stationary patterns - distributional changes, periodic shifts, and temporary fluctuations - in synthetic and logistics scenarios demonstrate its superiority over state-of-the-art baselines, confirming theoretical and practical robustness.
- Abstract（参考訳）: 報酬分布が動的に進化する非定常環境において、マルチアーマド・バンドイット(MAB)問題は困難である。
RAVEN-UCBは,理論的な厳密性と分散適応による実用的な効率性を組み合わせた新しいアルゴリズムである。
これは UCB1 や UCB-V よりも厳密な後悔境界を達成し、次数 $K \sigma_{\max}^2 \log T / \Delta$ のギャップ依存的後悔と次数 $\sqrt{K T \log T}$ のギャップ依存的後悔を達成している。
RAVEN-UCBは、(1)$\sqrt{\hat{\sigma}_k^2 / (N_k + 1)}$の信頼境界による分散駆動探索、(2)$\alpha_t = \alpha_0 / \log(t + \epsilon)$による適応制御、(3)効率のための定数時間再帰更新である。
合成および物流のシナリオにおいて、非定常パターン(分布変化、周期的シフト、一時的な変動)にわたる実験は、最先端のベースラインよりも優位性を示し、理論的および実用的な堅牢性を確認している。
関連論文リスト
- 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) - Sample Complexity of Variance-reduced Distributionally Robust Q-learning [17.96094201655567]
本稿では,分散性に頑健なQ-ラーニングアルゴリズムと,分散性に欠けるロバストなポリシーを効果的に学習できる分散性のあるQ-ラーニングアルゴリズムを2つ提案する。
一連の数値実験により、分布シフトの処理におけるアルゴリズムの理論的発見と効率性が確認された。
論文 参考訳（メタデータ） (2023-05-28T19:40:46Z) - Stability-penalty-adaptive follow-the-regularized-leader: Sparsity,
game-dependency, and best-of-both-worlds [46.30750729936261]
FTRL(Follow-the-regularized-leader)は近年,バンドイット問題における適応性獲得の最も有望なアプローチの1つである。
我々は3種類の適応性を持ついくつかのアルゴリズムを確立する:空間性、ゲーム依存性、およびベスト・オブ・ボス・ワールド(BOBW)である。
論文 参考訳（メタデータ） (2023-05-26T23:20:48Z) - Contextual Combinatorial Bandits with Probabilistically Triggered Arms [55.9237004478033]
確率的に誘発される腕(C$2$MAB-T)を様々な滑らかさ条件下で検討した。
トリガー変調 (TPM) 条件の下では、C$2$-UC-Tアルゴリズムを考案し、後悔すべき$tildeO(dsqrtT)$を導出する。
論文 参考訳（メタデータ） (2023-03-30T02:51:00Z) - Adversarially Robust Multi-Armed Bandit Algorithm with
Variance-Dependent Regret Bounds [34.37963000493442]
本稿では,マルチアーム・バンディット(MAB)問題について考察し,両対向的条件下でほぼ最適に機能する,新たなベスト・オブ・ボス・ワールド(BOBW)アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-06-14T12:58:46Z) - Rate-matching the regret lower-bound in the linear quadratic regulator
with unknown dynamics [6.287145010885044]
本稿では、O_p(sqrtT,textpolylog(T))$という新しい後悔の上限を確立する。
同時に$O_p(sqrtT,textpolylog(T))$の動的値に縛られる推定誤差を確立する。
論文 参考訳（メタデータ） (2022-02-11T17:50:14Z) - Near-Optimal No-Regret Learning for Correlated Equilibria in
Multi-Player General-Sum Games [104.74734408204749]
マルチプレイヤーの汎用正規形式ゲームにおいて,OMWU(Optimistic Multiplicative Weights Update)を用いているエージェントが全員,O(textrmpolylog(T))$(T$)$(T$)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$(OMWU)$)であることを示す。
外部の後悔から内部の後悔へと結果を拡張し、後悔を交換することで、近似した平衡に収束する非結合学習ダイナミクスを確立する。
論文 参考訳（メタデータ） (2021-11-11T01:19:53Z) - Restless-UCB, an Efficient and Low-complexity Algorithm for Online
Restless Bandits [61.490254407420906]
我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。
本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
論文 参考訳（メタデータ） (2020-11-05T05:16:04Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。