論文の概要: On the Precise Asymptotics and Refined Regret of the Variance-Aware UCB Algorithm
- arxiv url: http://arxiv.org/abs/2412.08843v1
- Date: Thu, 12 Dec 2024 00:44:43 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-12-13 13:29:30.928297
- Title: On the Precise Asymptotics and Refined Regret of the Variance-Aware UCB Algorithm
- Title(参考訳): 可変対応 UCB アルゴリズムの高精度漸近と精細化について
- Authors: Yuxuan Han, Xiaocong Xu,
- Abstract要約: 我々は,MAB問題に対するアッパー信頼境界変動(UCB-V)アルゴリズムの挙動について検討した。
UCB-Vは、より複雑で高度な分散を考慮したオンライン意思決定アルゴリズムにおいて、これまで知られていなかった、洗練された後悔の限界を達成できることを示す。
- 参考スコア(独自算出の注目度): 3.069335774032178
- License:
- Abstract: In this paper, we study the behavior of the Upper Confidence Bound-Variance (UCB-V) algorithm for Multi-Armed Bandit (MAB) problems, a variant of the canonical Upper Confidence Bound (UCB) algorithm that incorporates variance estimates into its decision-making process. More precisely, we provide an asymptotic characterization of the arm-pulling rates of UCB-V, extending recent results for the canonical UCB in Kalvit and Zeevi (2021) and Khamaru and Zhang (2024). In an interesting contrast to the canonical UCB, we show that the behavior of UCB-V can exhibit instability, meaning that the arm-pulling rates may not always be asymptotically deterministic. Besides the asymptotic characterization, we also provide non-asymptotic bounds for arm-pulling rates in the high probability regime, offering insights into regret analysis. As an application of this high probability result, we show that UCB-V can achieve a refined regret bound, previously unknown even for more complicate and advanced variance-aware online decision-making algorithms.
- Abstract(参考訳): 本稿では、分散推定を意思決定プロセスに組み込む標準的アッパー信頼境界(UCB)アルゴリズムの変種であるマルチアーマド・バンドイット(MAB)問題に対するアッパー信頼境界(UCB-V)アルゴリズムの挙動について検討する。
より正確には、UCB-Vの腕の拍動速度の漸近的評価を提供し、Kalvit and Zeevi (2021) と Khamaru and Zhang (2024) の標準 UCB の最近の結果を拡張した。
標準的 UCB とは対照的に,UCB-V の挙動は不安定であり,腕の脈動速度は漸近的に決定論的であるとは限らない。
漸近的特徴の他に、高確率状態におけるアーム推進速度の非漸近的境界も提供し、後悔の分析に関する洞察を提供する。
この高い確率結果の応用として,UPB-Vはより複雑で高度な分散を考慮したオンライン意思決定アルゴリズムであっても,これまで知られていなかった洗練された後悔の限界を達成できることを示す。
関連論文リスト
- UCB algorithms for multi-armed bandits: Precise regret and adaptive inference [6.349503549199403]
upper Confidence Bound (UCB) アルゴリズムは、$K$武器の盗聴問題に対して広く使われているシーケンシャルアルゴリズムのクラスである。
Lai-Robbins の後悔公式が真であることと、その部分最適性ギャップが$sigmasqrtKlog T/T$を超える場合に限ることを示す。
また、その最大後悔は対数係数によって最小後悔から逸脱し、従ってその厳密な最小最適性を負に設定することを示した。
論文 参考訳(メタデータ) (2024-12-09T01:14:02Z) - Best Arm Identification with Minimal Regret [55.831935724659175]
最高の腕識別問題 優雅にアマルガメートは、最小化とBAIを後悔している。
エージェントの目標は、所定の信頼度で最高の腕を特定することである。
二重KL-UCBアルゴリズムは、信頼度がゼロになる傾向があるため、最適性を達成する。
論文 参考訳(メタデータ) (2024-09-27T16:46:02Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
論文 参考訳(メタデータ) (2023-12-07T15:55:58Z) - On the Sublinear Regret of GP-UCB [58.25014663727544]
ガウス過程上信頼境界 (GP-UCB) アルゴリズムは, ほぼ最適の後悔率を有することを示す。
私たちの改善は、基盤となるカーネルの滑らかさに比例してカーネルリッジ推定を正規化するという、重要な技術的貢献に依存しています。
論文 参考訳(メタデータ) (2023-07-14T13:56:11Z) - Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である
本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。
PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
論文 参考訳(メタデータ) (2023-07-01T18:35:21Z) - On the Convergence of Black-Box Variational Inference [16.895490556279647]
完全ブラックボックス変分推論(BBVI)の最初の収束保証を提供する。
以上の結果より, 対数平滑な後部密度と対数凹凸が強く, 位置スケールの変動が認められなかった。
論文 参考訳(メタデータ) (2023-05-24T16:59:50Z) - Asymptotically Unbiased Instance-wise Regularized Partial AUC
Optimization: Theory and Algorithm [101.44676036551537]
One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。
既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。
本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
論文 参考訳(メタデータ) (2022-10-08T08:26:22Z) - Tuning Confidence Bound for Stochastic Bandits with Bandit Distance [5.818764911456228]
標準 UCB の「距離チューニング」は,提案した距離尺度を用いて行う。
探検バルゲインポイント」は、探検と搾取のトレードオフに関する洞察を与える。
論文 参考訳(メタデータ) (2021-10-06T12:24:07Z) - A Closer Look at the Worst-case Behavior of Multi-armed Bandit
Algorithms [8.099977107670918]
アッパー信頼境界 (UCB) は楽観的なMABアルゴリズムである。
本稿では,UCBのアームサンプリング動作に関する新しい知見を提供する。
また、UPBの下でのMAB問題のプロセスレベルの特徴付けも提供する。
論文 参考訳(メタデータ) (2021-06-03T20:52:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。