論文の概要: Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits
- arxiv url: http://arxiv.org/abs/2408.15535v1
- Date: Wed, 28 Aug 2024 04:56:06 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-29 17:12:56.260179
- Title: Improving Thompson Sampling via Information Relaxation for Budgeted Multi-armed Bandits
- Title(参考訳): 予算付きマルチアームバンドの情報緩和によるトンプソンサンプリングの改善
- Authors: Woojin Jeong, Seungki Min,
- Abstract要約: 我々は、各アームが選択時に異なるリソースを消費する、$Kの武器付きバンディット問題を考える。
我々はトンプソンサンプリングのようにランダム化される一連のアルゴリズムを提案するが、予算制約に関してより慎重に決定を最適化する。
- 参考スコア(独自算出の注目度): 1.4732811715354452
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider a Bayesian budgeted multi-armed bandit problem, in which each arm consumes a different amount of resources when selected and there is a budget constraint on the total amount of resources that can be used. Budgeted Thompson Sampling (BTS) offers a very effective heuristic to this problem, but its arm-selection rule does not take into account the remaining budget information. We adopt \textit{Information Relaxation Sampling} framework that generalizes Thompson Sampling for classical $K$-armed bandit problems, and propose a series of algorithms that are randomized like BTS but more carefully optimize their decisions with respect to the budget constraint. In a one-to-one correspondence with these algorithms, a series of performance benchmarks that improve the conventional benchmark are also suggested. Our theoretical analysis and simulation results show that our algorithms (and our benchmarks) make incremental improvements over BTS (respectively, the conventional benchmark) across various settings including a real-world example.
- Abstract(参考訳): 本稿では,各アームが選択時に異なる量の資源を消費し,使用可能な資源の総量に対する予算制約が存在する,ベイズ予算の多腕バンディット問題を考える。
予算付トンプソンサンプリング(英語版)(BTS)はこの問題に対して非常に効果的なヒューリスティックを提供するが、そのアーム選択規則は残りの予算情報を考慮していない。
我々は、古典的な$K$武器付きバンディット問題に対してトンプソンサンプリングを一般化する「textit{information Relaxation Smpling}」フレームワークを採用し、BTSのようにランダム化されるが、予算制約に関してより慎重に決定を最適化する一連のアルゴリズムを提案する。
これらのアルゴリズムとの1対1対応では、従来のベンチマークを改善する一連のパフォーマンスベンチマークも提案されている。
我々の理論解析とシミュレーションの結果から,実世界の実例を含む様々な環境において,BTSよりもアルゴリズム(およびベンチマーク)が漸進的に改善されていることが示唆された。
関連論文リスト
- Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳(メタデータ) (2023-12-13T11:08:25Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳(メタデータ) (2023-10-01T01:37:02Z) - Best Arm Identification for Stochastic Rising Bandits [84.55453174601826]
SRB(Rising Bandits)は、選択される度に選択肢の期待される報酬が増加する、シーケンシャルな意思決定の問題をモデル化する。
本稿では,SRBの固定予算ベストアーム識別(BAI)問題に焦点をあてる。
R-UCBE と R-SR の2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2023-02-15T08:01:37Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳(メタデータ) (2022-12-07T17:30:45Z) - Finding Optimal Arms in Non-stochastic Combinatorial Bandits with
Semi-bandit Feedback and Finite Budget [6.759124697337311]
有限サンプリング予算制約の下では,半帯域フィードバックによる帯域幅問題を考える。
アクションは、一組のアームを選択し、選択されたセット内の各アームに対するフィードバックが受信される。
本稿では,アーム除去戦略の全スペクトルをカバーするのに適した汎用アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-02-09T14:36:05Z) - Thompson Sampling for Bandits with Clustered Arms [7.237493755167875]
理論的および実験的に、与えられたクラスタ構造をどのように活用すれば、後悔と計算コストを大幅に改善できるかを示す。
我々のアルゴリズムは、以前に提案されたクラスタ化された腕を持つバンディットのアルゴリズムと比較してよく機能する。
論文 参考訳(メタデータ) (2021-09-06T08:58:01Z) - Bayesian decision-making under misspecified priors with applications to
meta-learning [64.38020203019013]
トンプソンサンプリングやその他のシーケンシャルな意思決定アルゴリズムは、文脈的包帯における探索と探索のトレードオフに取り組むための一般的なアプローチである。
性能は不特定な事前条件で優雅に低下することを示す。
論文 参考訳(メタデータ) (2021-07-03T23:17:26Z) - Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
本稿では、インテリジェントSMSルーティング問題と広告オーディエンス最適化問題という2つのアプリケーションを提案する。
既存のMABアルゴリズムの素早い一般化は、この問題に対してうまく機能しないことを示す。
また,このアルゴリズムに対して,探索定理の簡単な変種を提示し,ほぼ最適な後悔境界を定めている。
論文 参考訳(メタデータ) (2020-11-03T05:38:42Z) - 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) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。