論文の概要: Extended UCB Policies for Multi-armed Bandit Problems

• arxiv url: http://arxiv.org/abs/1112.1768v5
• Date: Mon, 15 Sep 2025 04:54:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-21 16:12:03.202955
• Title: Extended UCB Policies for Multi-armed Bandit Problems
• Title（参考訳）: マルチアームバンド問題に対する拡張UPB法
• Authors: Keqin Liu, Tianshuo Zheng, Zhi-Hua Zhou,
• Abstract要約: 我々は,古典的MABモデルと重み付き報酬分布について考察し,拡張された頑健な UCB ポリシーを導入する。 我々の拡張ロバスト UCB は、二つのモーメントが既知の制御関係を持つ限り、ラッティモアのセミナリーワークを任意の選択で$p>q>1$に一般化する。 約$p>1$に対して$p$-thのモーメントが存在する限り、報酬分布の知識がなければ、ほぼ最適の後悔順序を達成できる。
• 参考スコア（独自算出の注目度）: 46.390064640459
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The multi-armed bandit (MAB) problems are widely studied in fields of operations research, stochastic optimization, and reinforcement learning. In this paper, we consider the classical MAB model with heavy-tailed reward distributions and introduce the extended robust UCB policy, which is an extension of the results of Bubeck et al. [5] and Lattimore [22] that are further based on the pioneering idea of UCB policies [e.g. Auer et al. 3]. The previous UCB policies require some strict conditions on reward distributions, which can be difficult to guarantee in practical scenarios. Our extended robust UCB generalizes Lattimore's seminary work (for moments of orders $p=4$ and $q=2$) to arbitrarily chosen $p>q>1$ as long as the two moments have a known controlled relationship, while still achieving the optimal regret growth order $O(log T)$, thus providing a broadened application area of UCB policies for heavy-tailed reward distributions. Furthermore, we achieve a near-optimal regret order without any knowledge of the reward distributions as long as their $p$-th moments exist for some $p>1$. Finally, we briefly present our earlier work on light-tailed reward distributions for a complete illustration of the amazing simplicity and power of UCB policies.
• Abstract（参考訳）: マルチアーム・バンディット問題(MAB)は、運用研究、確率最適化、強化学習の分野で広く研究されている。 本稿では,大口径の報酬分布を持つ古典的MABモデルを考察し,より先駆的な UCB 政策の考え方に基づく Bubeck et al [5] と Lattimore [22] の結果の延長である拡張頑健な UCB ポリシーを導入する。 以前のUPBポリシーでは、報酬分布に関する厳格な条件を必要としており、現実的なシナリオでは保証が難しい。 我々の拡張ロバストな UCB は、ラッティモアのセミナリーな仕事(注文のモーメント$p=4$と$q=2$)を一般化し、2つのモーメントが既知の制御された関係を持つ限り、任意の選択をする$p>q>1$ とし、なおも最適な後悔の生長順序$O(log T)$ を達成し、重み付き報酬分布に対する UCB ポリシーの適用範囲を広げる。 さらに、約$p>1$に対して$p$-thのモーメントが存在する限り、報酬分布の知識がなければ、ほぼ最適の後悔順序を達成できる。 最後に、UCBポリシーの驚くべき単純さとパワーの完全な実例を示すために、光尾の報酬分布に関する以前の研究を簡潔に紹介する。

関連論文リスト

• Quick-Draw Bandits: Quickly Optimizing in Nonstationary Environments with Extremely Many Arms [80.05851139852311]
  本稿では,ガウス的手法を用いて連続空間上の報酬環境を学習するための新しいポリシーを提案する。 提案手法は,$mathcalO*(sqrtT)$ cumulative regret を用いて連続リプシッツ報酬関数を効率よく学習することを示す。
  論文  参考訳（メタデータ） (2025-05-30T15:15:18Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。 UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
  論文  参考訳（メタデータ） (2024-10-08T09:49:47Z)
• Data-Driven Upper Confidence Bounds with Near-Optimal Regret for Heavy-Tailed Bandits [0.0]
  対称な報酬分布のための分布自由データ駆動型 UCB アルゴリズムを提案する。 パラメータフリーなRMM-UCB法では,重み付き分布であっても,ほぼ最適の残差を証明した。
  論文  参考訳（メタデータ） (2024-06-09T10:06:50Z)
• Extreme Value Monte Carlo Tree Search [1.6574413179773757]
  UCB1 Multi-Armed Bandit (MAB)はドメインに依存しない計画において最近まで限られた成功を収めてきた。 UCB1-Uniform/Power という2つのバンドレットを提案し,それをモンテカルロ木探索 (MCTS) に適用して古典的計画を行う。
  論文  参考訳（メタデータ） (2024-05-28T14:58:43Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  逐次決定問題は、予測状態表現(PSR)によってモデル化された低ランク構造が認められる場合、統計的に学習可能である 本稿では,推定モデルと実モデル間の全変動距離を上限とする新しいボーナス項を特徴とする,PSRに対する最初のUCB型アプローチを提案する。 PSRに対する既存のアプローチとは対照的に、UCB型アルゴリズムは計算的トラクタビリティ、最優先の準最適ポリシー、モデルの精度が保証される。
  論文  参考訳（メタデータ） (2023-07-01T18:35:21Z)
• Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
  SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。 本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。 R-UCBE と R-SR の2つのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-02-15T08:01:37Z)
• Sample Complexity of an Adversarial Attack on UCB-based Best-arm Identification Policy [0.0]
  マルチアームバンディット(MAB)において,報酬に対する敵対的摂動の問題について検討する。 I focus on a adversarial attack to a UCB type best-arm identification policy applied to a MAB。
  論文  参考訳（メタデータ） (2022-09-13T02:31:30Z)
• Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
  提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。 本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
  論文  参考訳（メタデータ） (2021-12-08T02:20:18Z)
• Achieving the Pareto Frontier of Regret Minimization and Best Arm Identification in Multi-Armed Bandits [91.8283876874947]
  本稿では,BoBW-lil'UCB$(gamma)$アルゴリズムの設計と解析を行う。 i) RMとBAIの両方の目的に対して最適なアルゴリズムを同時に実行できないことを示す。 また、BoBW-lil'UCB$(gamma)$は、時間複雑性と後悔の点で競合よりも優れていることを示す。
  論文  参考訳（メタデータ） (2021-10-16T17:52:32Z)
• Reinforcement Learning in Reward-Mixing MDPs [74.41782017817808]
  報酬混合マルコフ決定過程(MDP)におけるエピソード強化学習 cdot S2 A2)$ episodes, where$H$ is time-horizon and $S, A$ are the number of state and actions。 epsilon$-optimal policy after $tildeO(poly(H,epsilon-1) cdot S2 A2)$ episodes, $H$ is time-horizon and $S, A$ are the number of state and actions。
  論文  参考訳（メタデータ） (2021-10-07T18:55:49Z)
• Addressing the Long-term Impact of ML Decisions via Policy Regret [49.92903850297013]
  意思決定者が腕を引っ張るたびに、各腕からの報酬が進化する状況について検討する。 我々は、許容可能な機会の逐次配分は、成長の可能性を考慮に入れなければならないと論じている。 十分に長い時間的地平線に対して、確実にサブ線形ポリシーを後悔するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-02T17:38:10Z)
• Combinatorial Bandits without Total Order for Arms [52.93972547896022]
  セット依存報酬分布を捕捉し、武器の合計順序を仮定しない報酬モデルを提案する。 我々は、新しい後悔分析を開発し、$Oleft(frack2 n log Tepsilonright)$ gap-dependent regret boundと$Oleft(k2sqrtn T log Tright)$ gap-dependent regret boundを示す。
  論文  参考訳（メタデータ） (2021-03-03T23:08:59Z)
• Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret [5.1398743023989555]
  我々は、各腕に関連する報酬の分布が時間変動であると仮定する非定常的マルチアーミングバンディット(MAB)問題を研究する。 提案手法は, 変動予算を満たした報酬分配系列の組に対する後悔の前提となる, 最悪の場合の後悔という観点から, 提案手法の性能を特徴付ける。
  論文  参考訳（メタデータ） (2021-01-22T07:34:09Z)
• Learning and Optimization with Seasonal Patterns [3.7578900993400626]
  平均報酬が周期的に変化するK$アームを持つ非定常MABモデルを考える。 本稿では,信頼関係分析と学習手順を組み合わせて未知の期間を学習する2段階ポリシーを提案する。 我々の学習ポリシーは、後悔の上限である $tildeO(sqrtTsum_k=1K T_k)$ ここで、$T_k$はarm $k$の期間であることを示す。
  論文  参考訳（メタデータ） (2020-05-16T20:19:25Z)
• Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition [59.34067736545355]
  有限水平型マルコフ決定過程(MDP)における強化学習問題を,S$状態,A$動作,エピソード長$H$を用いて検討した。 モデルフリーアルゴリズム UCB-Advantage を提案し、$T = KH$ および $K$ が再生すべきエピソード数である場合に $tildeO(sqrtH2SAT)$ regret を達成することを証明した。
  論文  参考訳（メタデータ） (2020-04-21T14:00:06Z)
• The Unreasonable Effectiveness of Greedy Algorithms in Multi-Armed Bandit with Many Arms [10.662105162882526]
  本研究は,Emphmany-armed regimeにおける$k$-armed bandit問題について考察する。 以上の結果から,多腕の環境下での強欲なアルゴリズムには,新たなエフェフリー探索法が有用であることが示唆された。
  論文  参考訳（メタデータ） (2020-02-24T08:59:34Z)

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

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