論文の概要: 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)に基づく政策を拡張し, ミニマックスの後悔, すなわち, いかなる政策でも達成される最低の最悪の後悔について, 秩序最適であることを示す。 また,報奨分布に対する下位ゲージの仮定を緩和し,重み付き報奨分布を処理し,その性能保証を維持することのできる,提案された警察の堅牢なバージョンを開発する。

関連論文リスト

• Likelihood Reward Redistribution [0.0]
  本稿では,報酬再分配のためのEmphLikelihood Reward Redistribution (LRR) フレームワークを提案する。 ソフトアクター・クライブのような非政治的アルゴリズムと統合すると、LRRは密度が高く情報的な報奨信号を生成する。
  論文  参考訳（メタデータ） (2025-03-20T20:50:49Z)
• 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)
• Stochastic Bandits for Egalitarian Assignment [58.33714486693828]
  我々は,多武装盗賊の文脈における平等的課題であるEgalMABについて検討する。 UCBベースのポリシーEgalUCBを設計・分析し、累積的後悔の上限を確立する。
  論文  参考訳（メタデータ） (2024-10-08T09:49:47Z)
• An Adaptive Approach for Infinitely Many-armed Bandits under Generalized Rotting Constraints [29.596684377841182]
  本研究では、休息状態において、アームの平均報酬が各プルで減少する可能性があるが、そうでなければ変化しない、無限に多くの武器を持つバンディット問題を考察する。 本稿では,ゆがみ報酬に起因するバイアスや分散トレードオフを管理するために,適応的なスライディングウィンドウを備えたUTBを利用するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-04-22T14:11:54Z)
• 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)
• 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)
• A Simple and Optimal Policy Design with Safety against Heavy-Tailed Risk for Stochastic Bandits [27.058087400790555]
  マルチアームバンディット問題について検討し,期待された後悔に対する最悪のケース最適性と,後悔の分布に対する軽微なリスクの両方を享受する新しいポリシーを設計する。 経営的な観点から、我々の新しい政策設計は、より良い尾の分布をもたらし、祝福された政策よりも好まれることがわかった。
  論文  参考訳（メタデータ） (2022-06-07T02:10:30Z)
• 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)

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

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