論文の概要: Adaptive KL-UCB based Bandit Algorithms for Markovian and i.i.d. Settings

• arxiv url: http://arxiv.org/abs/2009.06606v4
• Date: Sat, 8 Oct 2022 11:45:06 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-18 11:50:29.733601
• Title: Adaptive KL-UCB based Bandit Algorithms for Markovian and i.i.d. Settings
• Title（参考訳）: マルコフとi.d.設定のための適応KL-UCBに基づく帯域幅アルゴリズム
• Authors: Arghyadip Roy, Sanjay Shakkottai, R. Srikant
• Abstract要約: 両腕の報酬が真にマルコフ的か否かを識別する新しいアルゴリズムを導入する。 我々のアルゴリズムは、標準のKL-UCBからKL-UCBの特殊バージョンに切り換えるが、腕の報酬がマルコフ的であることを判断すると、i.d.とマルコフ的設定の両方に対する後悔は少なくなる。
• 参考スコア（独自算出の注目度）: 26.26185074977412
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In the regret-based formulation of Multi-armed Bandit (MAB) problems, except in rare instances, much of the literature focuses on arms with i.i.d. rewards. In this paper, we consider the problem of obtaining regret guarantees for MAB problems in which the rewards of each arm form a Markov chain which may not belong to a single parameter exponential family. To achieve a logarithmic regret in such problems is not difficult: a variation of standard Kullback-Leibler Upper Confidence Bound (KL-UCB) does the job. However, the constants obtained from such an analysis are poor for the following reason: i.i.d. rewards are a special case of Markov rewards and it is difficult to design an algorithm that works well independent of whether the underlying model is truly Markovian or i.i.d. To overcome this issue, we introduce a novel algorithm that identifies whether the rewards from each arm are truly Markovian or i.i.d. using a total variation distance-based test. Our algorithm then switches from using a standard KL-UCB to a specialized version of KL-UCB when it determines that the arm reward is Markovian, thus resulting in low regrets for both i.i.d. and Markovian settings.
• Abstract（参考訳）: 後悔に基づくマルチアームバンド問題(MAB)の定式化では、まれに例外を除いて、多くの文献は報酬の単位による武器に焦点を当てている。 本稿では、各アームの報酬が1つのパラメータ指数族に属さないマルコフ連鎖を形成するMAB問題に対する後悔の保証を得る問題を考察する。 このような問題における対数的後悔を達成することは難しくない:標準のkullback-leibler upper confidence bound (kl-ucb) のバリエーションが仕事を行う。 i.i.d.報酬はマルコフ報酬の特別な場合であり、基礎となるモデルが真にマルコフ的であるかi.i.d.であるかとは無関係に動作するアルゴリズムを設計することは困難であり、この問題を克服するために、各腕からの報酬が真にマルコフかi.i.dであるかを特定する新しいアルゴリズムを導入する。 我々のアルゴリズムは、標準のKL-UCBからKL-UCBの特殊バージョンに切り換えるが、腕の報酬がマルコフ的であることを判断すると、i.d.とマルコフ的設定の両方に対する後悔は少なくなる。

関連論文リスト

• Pure Exploration for Constrained Best Mixed Arm Identification with a Fixed Budget [6.22018632187078]
  固定予算の制約付きベスト・ミックスアーム識別(CBMAI)問題を導入する。 目標は、与えられた学習予算$N$で、期待されるコストの制約によって期待される報酬を最大化する最高の混合アームを見つけることである。 我々は、(最良の混合アームの支持の)誤識別に関する理論上の上限を提供し、予算$N$で指数関数的に崩壊することを示す。
  論文  参考訳（メタデータ） (2024-05-23T22:35:11Z)
• Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
  我々は、様々な武器の報酬間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。 特に、様々な武器の報酬の間の経験的ギャップに基づいて、あらゆるラウンドで腕を拒絶できる真に適応的なアルゴリズムであるsredを提示する。
  論文  参考訳（メタデータ） (2023-12-19T13:17:43Z)
• Forced Exploration in Bandit Problems [12.13966146283641]
  マルチアームバンディット(MAB)は古典的なシーケンシャルな決定問題である。 本稿では,報酬分布に関する情報を使わずに実装可能なマルチアームバンディットアルゴリズムを設計することを目的とする。
  論文  参考訳（メタデータ） (2023-12-12T14:00:29Z)
• Best Arm Identification in Restless Markov Multi-Armed Bandits [85.55466536537293]
  マルチアームバンディット環境における最適な腕を特定することの問題点について検討する。 決定エンティティは、上限誤差確率を条件として、ベストアームのインデックスをできるだけ早く見つけることを希望する。 このポリシーは、$R$に依存する上限を達成し、$Rtoinfty$として単調に増加しないことを示す。
  論文  参考訳（メタデータ） (2022-03-29T04:58:04Z)
• 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)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  我々は、各腕の状態がマルコフ連鎖に従って進化するオンラインレス・バンディット問題について研究する。 本研究では,探索研究の枠組みに従う学習方針であるReestless-UCBを提案する。
  論文  参考訳（メタデータ） (2020-11-05T05:16:04Z)
• Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
  我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。 我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。 我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2020-02-01T15:33:50Z)
• Finite-Time Analysis of Round-Robin Kullback-Leibler Upper Confidence Bounds for Optimal Adaptive Allocation with Multiple Plays and Markovian Rewards [10.66048003460524]
  本稿では,複数の演奏とマルコフ報酬を含む古典的マルチアームバンディット問題の拡張について検討する。 この問題に対処するために、各段階において、全てのアームのサンプル手段からの情報と、ラウンドロビン方式で選択された単一アームのクルバック・リーバー上信頼境界とを結合する適応的アロケーションルールを検討する。
  論文  参考訳（メタデータ） (2020-01-30T08:09:01Z)
• Regime Switching Bandits [5.520927473144736]
  本稿では,報酬が政権交代を示すマルチアームバンディット問題について検討する。 すべての腕から生じるランダムな報酬の分布は、有限状態マルコフ連鎖としてモデル化された共通の基底状態によって変調される。 そこで本研究では,隠れマルコフモデルに対するスペクトル法によるモーメント推定に基づく学習アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-01-26T02:50:56Z)

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

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