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

• arxiv url: http://arxiv.org/abs/1112.1768v4
• Date: Mon, 30 Jun 2025 04:15:58 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-07-06 14:52:02.556731
• Title: Extended UCB Policies for Frequentist Multi-armed Bandit Problems
• Title（参考訳）: 周波数多重武装バンディット問題に対する拡張UPB法
• Authors: Keqin Liu, Tianshuo Zheng, Zhi-Hua Zhou,
• Abstract要約: 本稿では主に,重み付き報酬分布を持つ古典的MABモデルについて考察する。 先駆的な UCB 政策の延長である, 堅牢な UCB 政策を導入する。
• 参考スコア（独自算出の注目度）: 49.1574468325115
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The multi-armed bandit (MAB) problem is a widely studied model in the field of operations research for sequential decision making and reinforcement learning. This paper mainly considers the classical MAB model with the heavy-tailed reward distributions. We introduce the extended robust UCB policy, which is an extension of the pioneering UCB policies proposed by Bubeck et al. [5] and Lattimore [22]. The previous UCB policies require some strict conditions on the reward distributions, which can be hard 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 the UCB policies for the 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$.
• Abstract（参考訳）: 多武装バンディット問題(英: multi-armed bandit problem、MAB)は、シーケンシャルな意思決定と強化学習のためのオペレーション研究の分野で広く研究されているモデルである。 本稿では主に,重み付き報酬分布を持つ古典的MABモデルについて考察する。 本稿では,Bubeck らによる UCB 政策の先駆的な拡張である,拡張堅牢な UCB 政策を紹介する。 以前のUPBポリシーでは、報酬分布に関する厳格な条件が必要であり、現実的なシナリオでは保証が難しい。 我々の拡張ロバストな UCB は、ラッティモアのセミナリーな作業(注文のモーメント$p=4$と$q=2$)を一般化し、2つのモーメントが既知の制御された関係を持つ限り、任意に選択した$p>q>1$ とし、なおも最適の後悔成長順序$O(log T)$ を達成し、重み付き報酬分布に対する UCB ポリシーの適用範囲を拡大する。 さらに、約$p>1$に対して$p$-thのモーメントが存在する限り、報酬分布の知識がなければ、ほぼ最適の後悔順序を達成できる。

関連論文リスト

• 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)

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

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