論文の概要: Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more

• arxiv url: http://arxiv.org/abs/2411.00339v1
• Date: Fri, 01 Nov 2024 03:39:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2024-11-05 14:44:17.416613
• Title: Unified theory of upper confidence bound policies for bandit problems targeting total reward, maximal reward, and more
• Title（参考訳）: 全報酬、最大報酬等を対象とする帯域問題に対する高信頼束縛政策の統一理論
• Authors: Nobuaki Kikkawa, Hiroshi Ohno,
• Abstract要約: 上位信頼境界(UCB)ポリシは、古典的全逆バンディット問題に対する順序最適解として認識される。 以上の結果から,UCB政策は全回帰問題と最大帯域幅問題の両方において順序最適性を実現する。 改善の可能性が最も高い腕を引くことを目的としたPIUCBアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.8287206589886879
• License:
• Abstract: The upper confidence bound (UCB) policy is recognized as an order-optimal solution for the classical total-reward bandit problem. While similar UCB-based approaches have been applied to the max bandit problem, which aims to maximize the cumulative maximal reward, their order optimality remains unclear. In this study, we clarify the unified conditions under which the UCB policy achieves the order optimality in both total-reward and max bandit problems. A key concept of our theory is the oracle quantity, which identifies the best arm by its highest value. This allows a unified definition of the UCB policy as pulling the arm with the highest UCB of the oracle quantity. Additionally, under this setting, optimality analysis can be conducted by replacing traditional regret with the number of failures as a core measure. One consequence of our analysis is that the confidence interval of the oracle quantity must narrow appropriately as trials increase to ensure the order optimality of UCB policies. From this consequence, we prove that the previously proposed MaxSearch algorithm satisfies this condition and is an order-optimal policy for the max bandit problem. We also demonstrate that new bandit problems and their order-optimal UCB algorithms can be systematically derived by providing the appropriate oracle quantity and its confidence interval. Building on this, we propose PIUCB algorithms, which aim to pull the arm with the highest probability of improvement (PI). These algorithms can be applied to the max bandit problem in practice and perform comparably or better than the MaxSearch algorithm in toy examples. This suggests that our theory has the potential to generate new policies tailored to specific oracle quantities.
• Abstract（参考訳）: 上位信頼境界(UCB)ポリシは、古典的全逆バンディット問題に対する順序最適解として認識される。 累積最大報酬を最大化することを目的とした最大バンディット問題に対して、同様の UCB ベースのアプローチが適用されているが、それらの順序の最適性は不明確である。 本研究では,UCB政策が全リワード問題と最大バンディット問題の両方において順序最適性を達成する統一条件を明らかにする。 我々の理論の鍵となる概念は、最高の腕を最も高い値で識別するオラクル量である。 これにより、UCBポリシーを最も高いUCB量で腕を引くものとして統一的に定義することができる。 さらに、この設定の下では、伝統的な後悔をコア尺度として失敗の数に置き換えることで、最適性分析を行うことができる。 分析の結果,UCBポリシーの順序最適性を確保するために,オラクル量の信頼区間を適宜狭めなければならないことがわかった。 この結果から,提案したMaxSearchアルゴリズムがこの条件を満たすことを示し,最大帯域幅問題に対する順序-最適ポリシーであることを示す。 また,新たなバンディット問題とその順序最適 UCB アルゴリズムは,適切なオラクル量とその信頼区間を提供することで,体系的に導出可能であることを示した。 そこで本研究では,最も高い改善率(PI)で腕を引くことを目的としたPIUCBアルゴリズムを提案する。 これらのアルゴリズムは、実際は最大バンディット問題に適用でき、おもちゃの例ではMaxSearchアルゴリズムよりも相容れないか、あるいは優れている。 このことは、我々の理論が特定のオラクル量に合わせて新しいポリシーを生成する可能性を持っていることを示唆している。

関連論文リスト

• e-COP : Episodic Constrained Optimization of Policies [12.854752753529151]
  本稿では,制約付き強化学習(RL)のための第1ポリシー最適化アルゴリズムを提案する。 提案アルゴリズムは, エピソード設定に適応したSoTA (non-episodic) アルゴリズムと類似あるいは良好な性能を示す。
  論文  参考訳（メタデータ） (2024-06-13T20:12:09Z)
• Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs [9.58750210024265]
  バンディットとマルコフ決定過程(MDP)に対する(確率的)ソフトマックスポリシー勾配(PG)法について検討する。 提案アルゴリズムは,技術結果と類似した理論的保証を提供するが,オラクルのような量の知識は必要としないことを示す。 マルチアームバンディット設定の場合,提案手法は明示的な探索や報奨ギャップの知識,報奨分布,ノイズを必要としない理論的なPGアルゴリズムを実現する。
  論文  参考訳（メタデータ） (2024-05-21T18:12:39Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Thompson Exploration with Best Challenger Rule in Best Arm Identification [66.33448474838342]
  本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。 我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
  論文  参考訳（メタデータ） (2023-10-01T01:37:02Z)
• Max-Min Grouped Bandits [48.62520520818357]
  マルチアームバンディット問題であるmax-min grouped banditsを導入する。 ゴールは、最悪の腕が最高の平均報酬を持つグループを見つけることです。 この問題はレコメンデーションシステムのようなアプリケーションには関心がある。
  論文  参考訳（メタデータ） (2021-11-17T01:59:15Z)
• Deep Upper Confidence Bound Algorithm for Contextual Bandit Ranking of Information Selection [0.0]
  CMAB(Contextual Multi-armed bandits)は、ユーザの関心に応じて情報のフィルタリングと優先順位付けを学習するために広く使用されている。 本研究は,トップKアームを反復的に選択して報酬を最大化するCMABフレームワークに基づくトップKランキングの分析である。 本稿では,Deep Up Confidence Bound (UCB)アルゴリズムという新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-10-08T13:32:14Z)
• On the Optimality of Batch Policy Optimization Algorithms [106.89498352537682]
  バッチポリシー最適化は、環境と対話する前に既存のデータをポリシー構築に活用することを検討する。 信頼調整インデックスアルゴリズムは楽観的,悲観的,中立的いずれであってもミニマックス最適であることを示す。 最適値予測の本来の難易度を考慮した新しい重み付き最小値基準を提案する。
  論文  参考訳（メタデータ） (2021-04-06T05:23:20Z)
• Upper Confidence Bounds for Combining Stochastic Bandits [52.10197476419621]
  バンディットアルゴリズムを結合する簡単な手法を提案する。 私たちのアプローチは、個々のbanditアルゴリズムのそれぞれを、より高いレベルのn$-armed bandit問題のアームとして扱う"meta-ucb"手順に基づいています。
  論文  参考訳（メタデータ） (2020-12-24T05:36:29Z)
• Best Arm Identification for Cascading Bandits in the Fixed Confidence Setting [81.70513857417106]
  CascadeBAIを設計し、分析する。これは、$K$アイテムのベストセットを見つけるアルゴリズムである。 CascadeBAIの時間的複雑さの上限は、決定的な分析課題を克服することによって導かれる。 その結果,カスケードBAIの性能は,時間的複雑性の低い境界の導出により,いくつかの実践的状況において最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-01-23T16:47:52Z)

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

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