論文の概要: Precise Asymptotics and Refined Regret of Variance-Aware UCB

• arxiv url: http://arxiv.org/abs/2412.08843v2
• Date: Sun, 16 Feb 2025 06:55:38 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-02-18 17:34:01.727660
• Title: Precise Asymptotics and Refined Regret of Variance-Aware UCB
• Title（参考訳）: UCBの高精度漸近と精細化
• Authors: Yingying Fan, Yuxuan Han, Jinchi Lv, Xiaocong Xu, Zhengyuan Zhou,
• Abstract要約: マルチアーメッド・バンドイット(MAB)問題に対するアッパー信頼境界変動(UCB-V)の挙動について検討した。 UCB-Vは不安定であり,腕拍動速度が常に決定論的であるとは限らないことが示唆された。 この高い確率結果の応用として、UCB-Vがより洗練された後悔境界を達成できることが確かめられる。
• 参考スコア（独自算出の注目度）: 18.05794171732746
• License:
• Abstract: In this paper, we study the behavior of the Upper Confidence Bound-Variance (UCB-V) algorithm for the 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 for 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, our analysis reveals 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 the arm-pulling rates in the high probability regime, offering insights into the regret analysis. As an application of this high probability result, we establish that UCB-V can achieve a more 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は、より複雑で高度な分散を考慮したオンライン意思決定アルゴリズムであっても、これまで知られていなかった、より洗練された後悔の限界を達成できることを示す。

関連論文リスト

• 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)
• Non-Asymptotic Analysis of a UCB-based Top Two Algorithm [4.18804572788063]
  バンディット識別のためのトップ2サンプリングルールは、2つの候補アームの中から次のアームを選択する方法である。 提案するUCBベースのトップ2は,非漸近的保証と競合経験性能を同時に享受する。
  論文  参考訳（メタデータ） (2022-10-11T13:21:59Z)
• 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)

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

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