論文の概要: Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits
- arxiv url: http://arxiv.org/abs/2410.05734v1
- Date: Tue, 8 Oct 2024 06:51:32 GMT
- ステータス: 処理完了
- システム内更新日: 2024-11-01 13:19:50.140526
- Title: Diminishing Exploration: A Minimalist Approach to Piecewise Stationary Multi-Armed Bandits
- Title（参考訳）: 最小限のマルチアーマッドバンドへのミニマリストアプローチ
- Authors: Kuan-Ta Li, Ping-Chun Hsieh, Yu-Chih Huang,
- Abstract要約: 片側定常バンドイット問題は、報酬分布の急激な変化を考察する。
既存のアルゴリズムは、変化点の数に関する知識を$M$とするか、非常に高い計算複雑性を必要とする。
そこで本研究では,MM$に関する知識の必要をなくす,減少探索と呼ばれる新奇で汎用的な探索機構を提案する。
- 参考スコア（独自算出の注目度）: 17.02018075805672
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The piecewise-stationary bandit problem is an important variant of the multi-armed bandit problem that further considers abrupt changes in the reward distributions. The main theme of the problem is the trade-off between exploration for detecting environment changes and exploitation of traditional bandit algorithms. While this problem has been extensively investigated, existing works either assume knowledge about the number of change points $M$ or require extremely high computational complexity. In this work, we revisit the piecewise-stationary bandit problem from a minimalist perspective. We propose a novel and generic exploration mechanism, called diminishing exploration, which eliminates the need for knowledge about $M$ and can be used in conjunction with an existing change detection-based algorithm to achieve near-optimal regret scaling. Simulation results show that despite oblivious of $M$, equipping existing algorithms with the proposed diminishing exploration generally achieves better empirical regret than the traditional uniform exploration.
- Abstract（参考訳）: ピースワイズ定常バンディット問題は、報酬分布の急激な変化を考察する多武装バンディット問題の重要な変種である。
問題の主なテーマは、環境変化を検出する探索と、従来のバンディットアルゴリズムの活用の間のトレードオフである。
この問題は広く研究されているが、既存の研究は変更点数に関する知識を$M$とするか、あるいは非常に高い計算複雑性を必要とする。
本研究では,ミニマリストの観点から,楽観的な帯域幅問題を再考する。
提案手法は,M$に関する知識を不要にし,既存の変化検出に基づくアルゴリズムと組み合わせて,ほぼ最適に後悔するスケーリングを実現することができる。
シミュレーションの結果は、$M(100万ドル)の難しさにもかかわらず、提案された探索の減少によって既存のアルゴリズムを取り入れることで、従来の一様探査よりも経験的な後悔を得られることを示している。
関連論文リスト
- Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Forced Exploration in Bandit Problems [12.13966146283641]
マルチアームバンディット(MAB)は古典的なシーケンシャルな決定問題である。
本稿では,報酬分布に関する情報を使わずに実装可能なマルチアームバンディットアルゴリズムを設計することを目的とする。
論文 参考訳（メタデータ） (2023-12-12T14:00:29Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳（メタデータ） (2023-10-02T08:15:52Z) - An Optimal Algorithm for the Real-Valued Combinatorial Pure Exploration
of Multi-Armed Bandit [65.268245109828]
多武装バンディット(R-CPE-MAB)の真価純探査問題について検討する。
既存のR-CPE-MABの手法は、いわゆるトランスダクティブ線形帯域の特殊な場合と見なすことができる。
本稿では,差分探索アルゴリズム (CombGapE) を提案する。
論文 参考訳（メタデータ） (2023-06-15T15:37:31Z) - Thompson Sampling with Virtual Helping Agents [0.0]
我々は、オンラインのシーケンシャルな意思決定の問題、すなわち、現在の知識を活用して即時パフォーマンスを最大化し、新しい情報を探索して長期的な利益を得るというトレードオフに対処する。
本稿では,マルチアームバンディット問題に対する2つのアルゴリズムを提案し,累積的後悔に関する理論的境界を提供する。
論文 参考訳（メタデータ） (2022-09-16T23:34:44Z) - Incentivizing Combinatorial Bandit Exploration [87.08827496301839]
自己関心のあるユーザに対してレコメンデーションシステムでアクションを推奨するバンディットアルゴリズムを考える。
ユーザーは他のアクションを自由に選択でき、アルゴリズムの推奨に従うためにインセンティブを得る必要がある。
ユーザは悪用を好むが、アルゴリズムは、前のユーザから収集した情報を活用することで、探索にインセンティブを与えることができる。
論文 参考訳（メタデータ） (2022-06-01T13:46:25Z) - Thompson Sampling on Asymmetric $\alpha$-Stable Bandits [0.0]
多腕バンディット問題は報酬分布を変化させることで提案した解を最適化することができる。
トンプソンサンプリングは、多武装バンディット問題を解決する一般的な方法である。
論文 参考訳（メタデータ） (2022-03-19T01:55:08Z) - On Slowly-varying Non-stationary Bandits [25.305949034527202]
我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。
我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。
我々のアルゴリズムは基本的にミニマックス最適であることを示す。
論文 参考訳（メタデータ） (2021-10-25T12:56:19Z) - Greedy Algorithm almost Dominates in Smoothed Contextual Bandits [100.09904315064372]
オンライン学習アルゴリズムは探索と搾取のバランスをとる必要がある。
欲求的アプローチは、他のアルゴリズムのベイズ的後悔率とほぼ一致していることを示す。
論文 参考訳（メタデータ） (2020-05-19T18:11:40Z) - Hyper-parameter Tuning for the Contextual Bandit [22.721128745617076]
本稿では,線形報酬関数の設定によるコンテキスト的帯域問題における探索的エクスプロイトトレードオフの学習問題について検討する。
提案アルゴリズムは,観測された文脈に基づいて,適切な探索パラメータをオンラインで選択することを学ぶ。
ここでは,文脈的帯域幅アルゴリズムの最適探索を求めるために,帯域幅を用いた2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-05-04T17:20:19Z) - The Price of Incentivizing Exploration: A Characterization via Thompson
Sampling and Sample Complexity [83.81297078039836]
インセンティブ付き探索(Incentivized Exploring)は、武器の選択を自給自足エージェントによって制御するマルチアーム・バンディットのバージョンである。
我々は、インセンティブの価格に焦点を合わせ、インセンティブの適合性のために、広く解釈された、パフォーマンスの喪失が引き起こされる。
論文 参考訳（メタデータ） (2020-02-03T04:58:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。