論文の概要: Last Switch Dependent Bandits with Monotone Payoff Functions
- arxiv url: http://arxiv.org/abs/2306.00338v1
- Date: Thu, 1 Jun 2023 04:38:32 GMT
- ステータス: 処理完了
- システム内更新日: 2023-06-02 18:21:54.522871
- Title: Last Switch Dependent Bandits with Monotone Payoff Functions
- Title（参考訳）: 単調ペイオフ機能を有する最後のスイッチ依存バンディット
- Authors: Ayoub Foussoul, Vineet Goyal, Orestis Papadigenopoulos, Assaf Zeevi
- Abstract要約: 我々は、LSDバンディット計画の近似性、すなわち、最適なアーム推進戦略を演算する(NP-hard)問題を理解するための一歩を踏み出した。
特に、この問題に対する最初の効率的な定数近似アルゴリズムを設計し、自然単調性仮定の下では、その近似が最先端にほぼ一致することを示す。
われわれは,新しい高次元緩和法や仮想状態の進化を反映する技術など,このような問題に対する新たなツールと洞察を開発する。
- 参考スコア（独自算出の注目度）: 8.860629791560198
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In a recent work, Laforgue et al. introduce the model of last switch
dependent (LSD) bandits, in an attempt to capture nonstationary phenomena
induced by the interaction between the player and the environment. Examples
include satiation, where consecutive plays of the same action lead to decreased
performance, or deprivation, where the payoff of an action increases after an
interval of inactivity. In this work, we take a step towards understanding the
approximability of planning LSD bandits, namely, the (NP-hard) problem of
computing an optimal arm-pulling strategy under complete knowledge of the
model. In particular, we design the first efficient constant approximation
algorithm for the problem and show that, under a natural monotonicity
assumption on the payoffs, its approximation guarantee (almost) matches the
state-of-the-art for the special and well-studied class of recharging bandits
(also known as delay-dependent). In this attempt, we develop new tools and
insights for this class of problems, including a novel higher-dimensional
relaxation and the technique of mirroring the evolution of virtual states. We
believe that these novel elements could potentially be used for approaching
richer classes of action-induced nonstationary bandits (e.g., special instances
of restless bandits). In the case where the model parameters are initially
unknown, we develop an online learning adaptation of our algorithm for which we
provide sublinear regret guarantees against its full-information counterpart.
- Abstract（参考訳）: 最近の研究で、Laforgueらは、プレイヤーと環境の間の相互作用によって引き起こされる非定常現象を捉えるために、最後のスイッチ依存(LSD)バンディットのモデルを導入した。
例えば、同じアクションの連続したプレイがパフォーマンスを低下させる風刺や、不活性化の期間後にアクションのペイオフが増加するデプリベーションなどがある。
本研究では,LSDブロードバンド計画の近似性,すなわち,モデルを完全に理解した最適なアーム推進戦略を計算する(NP-hard)問題を理解するための一歩を踏み出した。
特に,この問題に対する最初の効率的な定数近似アルゴリズムを設計し,自然単調性仮定の下では,その近似保証が,遅延依存(relay-dependent)と呼ばれる特別な,よく研究された帯状帯状体(recharging bandits)の最先端技術と一致することを示す。
本研究では,新しい高次元緩和法や仮想状態の進化を反映する技術など,この問題に対する新たなツールと洞察を開発する。
これらの新しい要素は、アクション誘発非定常バンディットのよりリッチなクラス(例えば、レストレスバンディットの特別なインスタンス)へのアプローチに使用できる可能性があると信じている。
モデルパラメータが未知である場合,本アルゴリズムのオンライン学習適応法を開発し,本アルゴリズムの完全情報に対するサブリニア後悔保証を提供する。
関連論文リスト
- Don't Miss Out on Novelty: Importance of Novel Features for Deep Anomaly
Detection [64.21963650519312]
異常検出(AD)は、正規性の学習モデルに適合しない観察を識別する重要なタスクである。
本稿では, 入力空間における説明不能な観測として, 説明可能性を用いた新しいAD手法を提案する。
当社のアプローチでは,複数のベンチマークにまたがる新たな最先端性を確立し,さまざまな異常な型を扱う。
論文 参考訳（メタデータ） (2023-10-01T21:24:05Z) - Towards Robust Continual Learning with Bayesian Adaptive Moment Regularization [51.34904967046097]
継続的な学習は、モデルが以前に学習した情報を忘れてしまう破滅的な忘れ込みの課題を克服しようとする。
本稿では,パラメータ成長の制約を緩和し,破滅的な忘れを減らし,新しい事前手法を提案する。
以上の結果から, BAdamは, 単頭クラスインクリメンタル実験に挑戦する先行手法に対して, 最先端の性能を達成できることが示唆された。
論文 参考訳（メタデータ） (2023-09-15T17:10:51Z) - Meta-Learning Adversarial Bandit Algorithms [55.72892209124227]
我々は,バンディットフィードバックを用いたオンラインメタラーニングについて研究する。
我々は自己協和障壁正規化器を用いてオンラインミラー降下一般化(OMD)をチューニングすることを学ぶ。
論文 参考訳（メタデータ） (2023-07-05T13:52:10Z) - Stochastic Rising Bandits [40.32303434592863]
本研究は、腕が単調に非減少している、安静時および安静時バンディットの特定の症例について検討する。
この特性により、ペイオフの規則性を利用して、厳密な後悔の限界を提供する、特別に構築されたアルゴリズムを設計することができる。
我々は,本アルゴリズムを実世界のデータセットに対するオンラインモデル選択問題や,複数の合成されたタスクに対する非定常MABの最先端手法と経験的に比較した。
論文 参考訳（メタデータ） (2022-12-07T17:30:45Z) - Non-Stationary Bandits under Recharging Payoffs: Improved Planning with
Sublinear Regret [34.44347218903429]
マルチアームバンディット設定は、最近非定常状態において研究されている。
各アクションの平均的なペイオフは、前回のプレイ以来のラウンド数の増加しない機能である。
我々は,我々のアルゴリズムがサブ線形後悔を伴う帯域幅アルゴリズムにどのように変換されるかを示す。
論文 参考訳（メタデータ） (2022-05-29T23:55:36Z) - FOSTER: Feature Boosting and Compression for Class-Incremental Learning [52.603520403933985]
ディープニューラルネットワークは、新しいカテゴリーを学ぶ際に破滅的な忘れ方に悩まされる。
本稿では,新たなカテゴリを適応的に学習するためのモデルとして,新しい2段階学習パラダイムFOSTERを提案する。
論文 参考訳（メタデータ） (2022-04-10T11:38:33Z) - Break your Bandit Routine with LSD Rewards: a Last Switch Dependent
Analysis of Satiation and Seasonality [6.146046338698175]
そこで本研究では,腕が最後に動作を切り替えて以降の時間経過によって,腕の期待される報酬が完全に決定される,新たな非定常バンディット問題を導入する。
我々のモデルは、遅延依存報酬の概念を一般化し、報酬関数に関するほとんどの仮定を緩和する。
我々はアルゴリズムを証明し、最適な非定常ポリシーに関してその後悔を証明した。
論文 参考訳（メタデータ） (2021-10-22T14:53:13Z) - Minimum-Delay Adaptation in Non-Stationary Reinforcement Learning via
Online High-Confidence Change-Point Detection [7.685002911021767]
非定常環境におけるポリシーを効率的に学習するアルゴリズムを導入する。
これは、リアルタイム、高信頼な変更点検出統計において、潜在的に無限のデータストリームと計算を解析する。
i) このアルゴリズムは, 予期せぬ状況変化が検出されるまでの遅延を最小限に抑え, 迅速な応答を可能にする。
論文 参考訳（メタデータ） (2021-05-20T01:57:52Z) - Non-Stationary Latent Bandits [68.21614490603758]
非定常ユーザに対して高速なパーソナライズのための実践的アプローチを提案する。
鍵となる考え方は、この問題を潜在バンディットとみなすことであり、ユーザ行動のプロトタイプモデルがオフラインで学習され、ユーザの潜伏状態がオンラインで推論される。
我々は,非定常潜伏帯域における後悔最小化のためのトンプソンサンプリングアルゴリズムを提案し,それらを解析し,実世界のデータセット上で評価する。
論文 参考訳（メタデータ） (2020-12-01T10:31:57Z) - Latent Bandits Revisited [55.88616813182679]
潜伏盗賊問題は、学習エージェントが未知の離散潜伏状態に条件付けられた腕の報酬分布を知知する問題である。
本稿では, 上位信頼境界(UCB)とトンプソンサンプリング(Thompson sample)の両方に基づいて, この設定のための一般的なアルゴリズムを提案する。
我々はアルゴリズムの統一的な理論的解析を行い、遅延状態の数がアクションよりも小さい場合、古典的なバンディットポリシーよりも後悔度が低い。
論文 参考訳（メタデータ） (2020-06-15T19:24:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。