論文の概要: 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)に基づく政策を拡張し, ミニマックスの後悔, すなわち, いかなる政策でも達成される最低の最悪の後悔について, 秩序最適であることを示す。
また,報奨分布に対する下位ゲージの仮定を緩和し,重み付き報奨分布を処理し,その性能保証を維持することのできる,提案された警察の堅牢なバージョンを開発する。
- 全文 参考訳へのリンク
関連論文リスト
- 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) - The Countable-armed Bandit with Vanishing Arms [8.099977107670918]
我々は、数え切れないほど多くの腕を有限個の「型」に分割したバンドイット問題を考える。
非定常分布は、腕の個体群における各腕型の相対的な存在量を支配しており、いわゆる「腕貯水池」である。
論文 参考訳(メタデータ) (2021-10-23T02:47:55Z) - Break your Bandit Routine with LSD Rewards: a Last Switch Dependent
Analysis of Satiation and Seasonality [6.146046338698175]
そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。
我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。
我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
論文 参考訳(メタデータ) (2021-10-22T14:53:13Z) - Dare not to Ask: Problem-Dependent Guarantees for Budgeted Bandits [66.02233330016435]
後悔と質問されたフィードバックの両方について、問題に依存した保証を提供します。
本稿では,問題依存的後悔と累積的フィードバック境界を導出するBuFALUというアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-10-12T03:24:57Z) - Policy Gradient Bayesian Robust Optimization for Imitation Learning [49.881386773269746]
我々は、期待される性能とリスクのバランスをとるために、新しいポリシー勾配スタイルのロバスト最適化手法PG-BROILを導出する。
その結果,PG-BROILはリスクニュートラルからリスク・アバースまでの行動のファミリを創出できる可能性が示唆された。
論文 参考訳(メタデータ) (2021-06-11T16:49:15Z) - Universal Off-Policy Evaluation [64.02853483874334]
ユニバーサルオフ政治推定器(UnO)への第一歩を踏み出す
我々は, 平均, 分散, 分位数/中間数, 分位数範囲, cvar, および累積分布全体の推定と同時結合に uno を用いる。
論文 参考訳(メタデータ) (2021-04-26T18:54:31Z) - Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
問合せ予算で意思決定問題を定式化する。
我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。
我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
論文 参考訳(メタデータ) (2021-02-05T19:56:31Z) - Off-Policy Evaluation of Slate Policies under Bayes Risk [70.10677881866047]
スレートのスロット上でロギングポリシーが因子化される典型的なケースにおいて、スレート帯のオフポリシ評価の問題について検討する。
PIによるリスク改善はスロット数とともに線形に増加し、スロットレベルの分岐の集合の算術平均と調和平均とのギャップによって線形に増加することを示す。
論文 参考訳(メタデータ) (2021-01-05T20:07:56Z) - Risk-Sensitive Deep RL: Variance-Constrained Actor-Critic Provably Finds
Globally Optimal Policy [91.44514047017954]
平均報酬設定下でのリスクに敏感な深層強化学習を,分散リスク基準を用いて初めて検討する。
ポリシ,ラグランジュ乗算器,フェンチェル双変数を反復的かつ効率的に更新するアクタークリティカルアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-12-28T05:02:26Z) - A One-Size-Fits-All Solution to Conservative Bandit Problems [32.907883501286]
我々は、サンプルパス報酬制約を伴う保守的なバンディット問題(CBP)のファミリーについて研究する。
CBPに対するOne-Size-Fits-Allソリューションを提案し、その応用を3つの包括問題に提示する。
論文 参考訳(メタデータ) (2020-12-14T08:50:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。