論文の概要: Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret

• arxiv url: http://arxiv.org/abs/2101.08980v1
• Date: Fri, 22 Jan 2021 07:34:09 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-21 04:38:12.824596
• Title: Nonstationary Stochastic Multiarmed Bandits: UCB Policies and Minimax Regret
• Title（参考訳）: 非定常確率的多腕バンディット:ucb政策とミニマックス後悔
• Authors: Lai Wei and Vaibhav Srivastava
• Abstract要約: 我々は、各腕に関連する報酬の分布が時間変動であると仮定する非定常的マルチアーミングバンディット(MAB)問題を研究する。 提案手法は, 変動予算を満たした報酬分配系列の組に対する後悔の前提となる, 最悪の場合の後悔という観点から, 提案手法の性能を特徴付ける。
• 参考スコア（独自算出の注目度）: 5.1398743023989555
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: We study the nonstationary stochastic Multi-Armed Bandit (MAB) problem in which the distribution of rewards associated with each arm are assumed to be time-varying and the total variation in the expected rewards is subject to a variation budget. The regret of a policy is defined by the difference in the expected cumulative rewards obtained using the policy and using an oracle that selects the arm with the maximum mean reward at each time. We characterize the performance of the proposed policies in terms of the worst-case regret, which is the supremum of the regret over the set of reward distribution sequences satisfying the variation budget. We extend Upper-Confidence Bound (UCB)-based policies with three different approaches, namely, periodic resetting, sliding observation window and discount factor and show that they are order-optimal with respect to the minimax regret, i.e., the minimum worst-case regret achieved by any policy. We also relax the sub-Gaussian assumption on reward distributions and develop robust versions the proposed polices that can handle heavy-tailed reward distributions and maintain their performance guarantees.
• Abstract（参考訳）: 本稿では,各アームに関連付けられた報酬の分布を時間的変化と仮定し,期待される報酬の総変動を変動予算に含める非定常確率的マルチアーメッドバンド(MAB)問題について検討する。 ポリシーの後悔は、ポリシーを使って得られた期待される累積報酬と、各時点の最大平均報酬を持つ腕を選択するオラクルとの差によって定義される。 提案手法は, 変動予算を満たした報酬分配系列の組に対する後悔の前提となる, 最悪の場合の後悔という観点から, 提案手法の性能を特徴付ける。 我々は, 周期的リセット, スライディング観察窓, ディスカウント係数という3つのアプローチにより, 上信頼境界(ucb)に基づく政策を拡張し, ミニマックスの後悔, すなわち, いかなる政策でも達成される最低の最悪の後悔について, 秩序最適であることを示す。 また,報奨分布に対する下位ゲージの仮定を緩和し,重み付き報奨分布を処理し,その性能保証を維持することのできる,提案された警察の堅牢なバージョンを開発する。

関連論文リスト

• Continuous K-Max Bandits [54.21533414838677]
  我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。 この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。 我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
  論文  参考訳（メタデータ） (2025-02-19T06:37:37Z)
• Catoni Contextual Bandits are Robust to Heavy-tailed Rewards [31.381627608971414]
  頑健な統計量からカトニ推定器上にアルゴリズム的アプローチを構築する。 我々は、累積的な報酬分散と対数的に報酬範囲の$R$にのみ依存する後悔境界を確立する。 アルゴリズムはまた、対数的報酬範囲依存を伴う分散ベースのバウンダリも享受する。
  論文  参考訳（メタデータ） (2025-02-04T17:03:32Z)
• Constrained Best Arm Identification in Grouped Bandits [3.387374559368306]
  そこで本研究では,各アームが複数の独立したサブアームから構成されるグループバンドセットについて検討する。 我々は、腕が実現可能であるとみなすためには、その属性のすべての平均報酬が指定された閾値を超えるべきであるという制約を課す。 ゴールは、固定された信頼設定において、実現可能な腕のセットの中で、属性の平均的な報酬が最大となる腕を見つけることである。
  論文  参考訳（メタデータ） (2024-12-11T02:19:19Z)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。 UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
  論文  参考訳（メタデータ） (2024-10-08T09:49:47Z)
• Budgeted Multi-Armed Bandits with Asymmetric Confidence Intervals [0.9831489366502302]
  予算的マルチアーマッド・バンドイット(MAB)問題について検討し、プレイヤーが期待できない報酬とコストでK$アームから選択する。 非対称な信頼区間を用いた新しいアッパー信頼境界(UCB)サンプリングポリシーである$omega$-UCBを提案する。 これらの間隔は、サンプル平均とランダム変数の境界との間の距離でスケールし、報酬コスト比をより正確かつ厳密に推定する。
  論文  参考訳（メタデータ） (2023-06-12T12:35:16Z)
• Contextual bandits with concave rewards, and an application to fair ranking [108.48223948875685]
  CBCR (Contextual Bandits with Concave Rewards) に対する反省点のある最初のアルゴリズムを提案する。 我々は,スカラー・リワード問題に対するCBCRの後悔から,新たな縮小を導出した。 推薦の公正さによって動機づけられたCBCRの特別事例として,ランク付けと公正を意識した目的について述べる。
  論文  参考訳（メタデータ） (2022-10-18T16:11:55Z)
• Stochastic differential equations for limiting description of UCB rule for Gaussian multi-armed bandits [0.0]
  制御地平線サイズが既知の多腕バンディットの高信頼バウンド戦略をN$とみなす。 平均報酬が次数$N-1/2$で異なる場合, 報酬の密分布に対してモンテカルロシミュレーションを行った。 正規化された後悔が最大値よりも顕著に大きくないときの制御水平方向の最小サイズを推定した。
  論文  参考訳（メタデータ） (2021-12-13T05:24:59Z)
• Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
  我々は、期待される性能とリスクのバランスをとるために、新しいポリシー勾配スタイルのロバスト最適化手法PG-BROILを導出する。 その結果,PG-BROILはリスクニュートラルからリスク・アバースまでの行動のファミリを創出できる可能性が示唆された。
  論文  参考訳（メタデータ） (2021-06-11T16:49:15Z)
• Minimax Policy for Heavy-tailed Bandits [10.203602318836444]
  我々は、飽和経験平均を用いて、ガウス以下の報酬分布に対するミニマックスポリシー MOSS を修正し、ロバスト MOSS と呼ばれる新しいアルゴリズムを設計する。 報酬分布に対する1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1+エプシロン=1。
  論文  参考訳（メタデータ） (2020-07-20T21:43:57Z)
• Adaptive Discretization for Adversarial Lipschitz Bandits [85.39106976861702]
  リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。 ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。 逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
  論文  参考訳（メタデータ） (2020-06-22T16:06:25Z)
• Robustness Guarantees for Mode Estimation with an Application to Bandits [131.21717367564963]
  平均ではなく報酬分布のモードを値とするマルチアームバンディットの理論を導入する。 我々は,我々のアルゴリズムが逆雑音列による腕の摂動に頑健であることを示すシミュレーションで示す。
  論文  参考訳（メタデータ） (2020-03-05T21:29:27Z)

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

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