論文の概要: Generalized non-stationary bandits
- arxiv url: http://arxiv.org/abs/2102.00725v1
- Date: Mon, 1 Feb 2021 09:34:44 GMT
- ステータス: 処理完了
- システム内更新日: 2021-02-02 15:40:13.376897
- Title: Generalized non-stationary bandits
- Title(参考訳): 一般化非定常バンディット
- Authors: Anne Gael Manegueu, Alexandra Carpentier and Yi Yu
- Abstract要約: スイッチングバンドイット問題を一般化する非定常バンドイット問題について検討する。
本稿では, 4つの問題 (a)-(d) を効率よく, 統一的に解く単一アルゴリズムを提案する。
- 参考スコア(独自算出の注目度): 78.05847530997926
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In this paper, we study a non-stationary stochastic bandit problem, which
generalizes the switching bandit problem. On top of the switching bandit
problem (\textbf{Case a}), we are interested in three concrete examples:
(\textbf{b}) the means of the arms are local polynomials, (\textbf{c}) the
means of the arms are locally smooth, and (\textbf{d}) the gaps of the arms
have a bounded number of inflexion points and where the highest arm mean cannot
vary too much in a short range. These three settings are very different, but
have in common the following: (i) the number of similarly-sized level sets of
the logarithm of the gaps can be controlled, and (ii) the highest mean has a
limited number of abrupt changes, and otherwise has limited variations. We
propose a single algorithm in this general setting, that in particular solves
in an efficient and unified way the four problems (a)-(d) mentioned.
- Abstract(参考訳): 本稿では,スイッチングバンドイット問題を一般化する非定常確率バンドイット問題について検討する。
スイッチングバンドイット問題(\textbf{Case a})に加えて、我々は3つの具体的な例に興味を持っている: (\textbf{b}) 腕の手段は局所多項式であり、 (\textbf{c}) 腕の手段は局所的に滑らかであり、 (\textbf{d}) 腕の隙間は束縛された数の屈曲点を持ち、そこでは最も高い腕の平均は短い範囲であまり変化しない。
これらの3つの設定は非常に異なるが、共通する点がある: (i) ギャップの対数の同様の大きさのレベル集合の数を制御でき、 (ii) 最高平均は急な変更の数に制限があり、それ以外は変化が限られている。
この一般的な設定では、特に4つの問題 (a)-(d) を効率的かつ統一的に解く1つのアルゴリズムを提案する。
関連論文リスト
- A General Framework for Clustering and Distribution Matching with Bandit Feedback [81.50716021326194]
我々は,帯域幅フィードバックを用いたクラスタリングと分散マッチング問題のための一般的なフレームワークを開発する。
誤り確率が$delta$を超えない任意のオンラインアルゴリズムに対して、平均アームプル数に基づいて漸近的でない下界を導出する。
我々の洗練された分析により、アルゴリズムの平均的なアームプル数が、$delta$が消えるにつれて、基本的限界に収束する速度に縛られる新しい現象が明らかになった。
論文 参考訳(メタデータ) (2024-09-08T12:19:12Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
論文 参考訳(メタデータ) (2023-12-19T13:17:43Z) - Max-Quantile Grouped Infinite-Arm Bandits [39.7239093424124]
無限に多くの腕からなる群が多数存在するバンド問題。
本稿では,まず各グループから一定数のアームを要求し,次に有限腕グループ化された最大量子帯域幅アルゴリズムを実行する2段階アルゴリズムを提案する。
インスタンス依存と最悪のケースの後悔の両方を特徴付け、後者に一致する下位境界を提供します。
論文 参考訳(メタデータ) (2022-10-04T00:46:49Z) - Best Arm Identification under Additive Transfer Bandits [49.69203462561861]
提案手法は, 未知であるにもかかわらず, ソースとターゲットMABインスタンスの間には, 付加的な関係があることが知られている。
本稿では,LUCBスタイルのアルゴリズムを理論的に解析し,高い確率で$epsilon$-optimal target armを同定する。
論文 参考訳(メタデータ) (2021-12-08T02:20:18Z) - Problem Dependent View on Structured Thresholding Bandit Problems [73.70176003598449]
我々は、Thresholding Bandit problem (TBP)における問題依存体制について検討する。
学習者の目的は、シーケンシャルゲームの終わりに、所定のしきい値を超える手段を持つアームセットを出力することである。
コンケーブ設定と単調設定の両方で誤差の確率を上下に設定する。
論文 参考訳(メタデータ) (2021-06-18T15:01:01Z) - From Finite to Countable-Armed Bandits [8.099977107670918]
有限の型に属する数え切れないほど多くのアームを持つバンドイット問題を考える。
武器の集団のそれぞれの種類の割合を設定する型に一定の分布がある。
我々は,O(log n)分布依存的な累積後悔を任意の回数の再生後に達成する完全適応型オンライン学習アルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-05-22T13:09:50Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳(メタデータ) (2021-05-22T02:46:04Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-23T19:52:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。