論文の概要: On Slowly-varying Non-stationary Bandits
- arxiv url: http://arxiv.org/abs/2110.12916v1
- Date: Mon, 25 Oct 2021 12:56:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-10-26 14:41:07.938805
- Title: On Slowly-varying Non-stationary Bandits
- Title(参考訳): 緩慢な非定常バンディットについて
- Authors: Ramakrishnan Krishnamurthy, Aditya Gopalan
- Abstract要約: 我々は、ゆっくりと変化する性質を持つ非定常包帯の動的後悔を考察する。
我々は、ゆっくりと変化する非定常帯域に対して、最初のインスタンス依存後悔上限を確立する。
我々のアルゴリズムは基本的にミニマックス最適であることを示す。
- 参考スコア(独自算出の注目度): 25.305949034527202
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider minimisation of dynamic regret in non-stationary bandits with a
slowly varying property. Namely, we assume that arms' rewards are stochastic
and independent over time, but that the absolute difference between the
expected rewards of any arm at any two consecutive time-steps is at most a
drift limit $\delta > 0$. For this setting that has not received enough
attention in the past, we give a new algorithm which extends naturally the
well-known Successive Elimination algorithm to the non-stationary bandit
setting. We establish the first instance-dependent regret upper bound for
slowly varying non-stationary bandits. The analysis in turn relies on a novel
characterization of the instance as a detectable gap profile that depends on
the expected arm reward differences. We also provide the first minimax regret
lower bound for this problem, enabling us to show that our algorithm is
essentially minimax optimal. Also, this lower bound we obtain matches that of
the more general total variation-budgeted bandits problem, establishing that
the seemingly easier former problem is at least as hard as the more general
latter problem in the minimax sense. We complement our theoretical results with
experimental illustrations.
- Abstract(参考訳): 緩やかに変化する特性を有する非定常バンディットにおける動的後悔の最小化を検討する。
すなわち、アームの報酬は時間とともに確率的かつ独立であると仮定するが、任意の2つの連続するタイムステップにおける任意のアームの報酬の絶対差は、ドリフト極限$\delta > 0$である。
過去に十分な注意を払わなかったこの設定に対しては、よく知られた逐次除去アルゴリズムを非定常帯域設定に自然に拡張する新しいアルゴリズムを提案する。
我々は、ゆっくりと変化する非定常帯域に対する最初のインスタンス依存後悔上限を確立する。
この分析は、予想される腕の報酬差に依存する検出可能なギャッププロファイルとして、インスタンスの新たな特徴に依存している。
また、この問題に対する最初のミニマックス後悔の最小境界を提供し、アルゴリズムが本質的にミニマックス最適であることを示す。
また、この下界は、より一般的な総変量予算のバンディット問題と一致し、一見簡単な以前の問題は、ミニマックス感覚のより一般的な後者問題と同程度に困難であることを示す。
我々は実験的なイラストで理論結果を補完する。
関連論文リスト
- Multi-Armed Bandits with Abstention [62.749500564313834]
本稿では, 新たな戦略要素である禁忌を取り入れた, 正準多重武装バンディット問題の拡張を提案する。
この強化されたフレームワークでは、エージェントは各タイムステップでアームを選択することだけでなく、観察する前に即時報酬を受け付けないオプションも備えている。
論文 参考訳(メタデータ) (2024-02-23T06:27:12Z) - The price of unfairness in linear bandits with biased feedback [62.25313751895011]
線形帯域フィードバックによる逐次意思決定の問題点について検討する。
その結果,不偏フィードバック下で得られたdT 1/2 log(T) の後悔率よりも最悪の後悔率が高いことがわかった。
興味深いことに、ギャップ依存率によって、問題はバイアスのないものほど難しくない非自明なインスタンスの存在が明らかになる。
論文 参考訳(メタデータ) (2022-03-18T08:03:20Z) - Nonstochastic Bandits with Composite Anonymous Feedback [41.38921728211769]
本研究では,アクションの損失が直ちにプレイヤーに請求されない非確率的バンディット設定について検討する。
各ラウンドの最後にプレイヤーが観測した瞬間的な損失は、これまでプレイされたアクションの多くの損失成分の合計である。
論文 参考訳(メタデータ) (2021-12-06T08:44:04Z) - Combinatorial Blocking Bandits with Stochastic Delays [33.65025386998747]
最近の研究は、各腕の報酬が最後の引き抜きから経過した時間の特別な機能であるマルチアームバンディット問題の自然変化を考察している。
本研究では, 上記のモデルを2つの方向に拡張する。 (i) 各ラウンドで複数の腕を演奏できる汎用的な設定を, 実現可能性制約の下で検討する。
我々は、利用可能な(非ブロック化された)アームの中で、常に最大で期待される報酬を再生する自然な欲求部分集合の近似を厳密に分析する。
腕の期待報酬が不明な場合、上記のアルゴリズムを盗賊に適応させる。
論文 参考訳(メタデータ) (2021-05-22T02:46:04Z) - Be Greedy in Multi-Armed Bandits [22.301793734117805]
グレディアルゴリズムは、各ラウンドで局所最適選択を行う、シーケンシャルな決定問題の最も単純なものである。
We provide a generic worst-case bound on the regret of the Greedy algorithm。
連続・無限・多武装バンディット問題において,ほぼ最適の最悪の後悔境界を検証できることを証明した。
論文 参考訳(メタデータ) (2021-01-04T16:47:02Z) - A Regret bound for Non-stationary Multi-Armed Bandits with Fairness
Constraints [7.716156977428555]
我々は,緩やかに変化する$k$-armed bandit問題を解くために,fair upper confidenceと呼ばれる新しいアルゴリズムとexploring fair-ucbeを提案する。
非定常ケースにおけるアルゴリズムの性能は,その定常ケースに近づくとゼロになりがちであることを示す。
論文 参考訳(メタデータ) (2020-12-24T18:12:01Z) - Lenient Regret for Multi-Armed Bandits [72.56064196252498]
エージェントが順番に行動を選択し、その行動に対する報酬を観察するマルチアーマッド・バンディット(MAB)問題を考察する。
アルゴリズムの大多数は、後悔、すなわち最高の行動の報酬とエージェントの行動の累積的な差を最小化しようとするが、この基準は望ましくない結果をもたらすかもしれない。
我々は、いくつかの$epsilon$よりも小さな最適性ギャップを無視した、より寛大で寛大で後悔すべき基準を提案する。
論文 参考訳(メタデータ) (2020-08-10T08:30:52Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z) - Optimal Best-arm Identification in Linear Bandits [79.3239137440876]
サンプルの複雑さが既知のインスタンス固有の下界と一致する単純なアルゴリズムを考案する。
既存のベストアーム識別戦略とは異なり、我々のアルゴリズムは武器の数に依存しない停止規則を用いる。
論文 参考訳(メタデータ) (2020-06-29T14:25:51Z) - On Regret with Multiple Best Arms [12.315392649501101]
バンディット設定における複数のベスト/ニア最適アームの存在に関する後悔問題について検討する。
我々の目標は、問題の未知の硬さに自動的に適応できるアルゴリズムを設計することです。
論文 参考訳(メタデータ) (2020-06-26T04:01:46Z) - A Novel Confidence-Based Algorithm for Structured Bandits [129.30402124516507]
両腕の報酬が他の腕の報酬と相関する可能性のある有限腕包帯について検討した。
本稿では、与えられた構造を利用して、真のバンディット問題のパラメータに対する信頼セットを構築する新しい位相アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-05-23T19:52:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。