論文の概要: On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
- arxiv url: http://arxiv.org/abs/2603.18514v1
- Date: Thu, 19 Mar 2026 05:47:57 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-20 17:19:05.975421
- Title: On the Peril of (Even a Little) Nonstationarity in Satisficing Regret Minimization
- Title（参考訳）: 満足度レジスト最小化における(小さなときも)非定常性の影響について
- Authors: Yixuan Zhang, Ruihao Zhu, Qiaomin Xie,
- Abstract要約: 固定セグメントが$L$である一般実現可能かつ断片的な定常設定において、最適後悔は$(Llog T)$で$Lgeq 2$であることを示す。
本分析の鍵となる要素は,非定常バンディットに適した新規なファノ系フレームワークである。
- 参考スコア（独自算出の注目度）: 20.199782529861913
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Motivated by the principle of satisficing in decision-making, we study satisficing regret guarantees for nonstationary $K$-armed bandits. We show that in the general realizable, piecewise-stationary setting with $L$ stationary segments, the optimal regret is $Θ(L\log T)$ as long as $L\geq 2$. This stands in sharp contrast to the case of $L=1$ (i.e., the stationary setting), where a $T$-independent $Θ(1)$ satisficing regret is achievable under realizability. In other words, the optimal regret has to scale with $T$ even if just a little nonstationarity presents. A key ingredient in our analysis is a novel Fano-based framework tailored to nonstationary bandits via a \emph{post-interaction reference} construction. This framework strictly extends the classical Fano method for passive estimation as well as recent interactive Fano techniques for stationary bandits. As a complement, we also discuss a special regime in which constant satisficing regret is again possible.
- Abstract（参考訳）: 意思決定における満足感の原則に感銘を受けて,我々は,非定常的な$K$武器の盗賊に対する後悔の保証を満足させる研究を行った。
固定セグメントが$L$である一般実現可能かつ断片的な定常設定において、最適の後悔は$L(L\log T)$で$L\geq 2$であることを示す。
これは、$L=1$(つまり定常的な設定)の場合とは対照的であり、$T$非独立な$...(1)$ 後悔を満足させることは実現可能である。
言い換えれば、最適の後悔は、ほんの少しの非定常性が存在するとしても、$T$でスケールしなければならない。
本分析の鍵となる要素は,非定常バンディットに適した新規なファノベースフレームワークである。
この枠組みは、受動的推定のための古典的ファノ法を厳密に拡張し、また、定常的包帯に対する最近の対話的ファノ法も拡張した。
また, 補足として, 絶え間ない後悔が再び可能となる特別な体制についても論じる。
関連論文リスト
- Near-Optimal Regret for KL-Regularized Multi-Armed Bandits [54.77408659142336]
KL正規化目標に対するオンライン学習の統計的効率について検討する。
我々は、MABsのKL正規化後悔が$$非依存であることを示し、$tilde(sqrtKT)$とスケールする。
論文 参考訳（メタデータ） (2026-03-02T18:17:33Z) - Catoni-Style Change Point Detection for Regret Minimization in Non-Stationary Heavy-Tailed Bandits [31.212504858546232]
ヘビーテールの片側定常バンディット問題に対処する。
重み付き分布に適した新しいカタニスタイル変化点検出戦略を提案する。
本稿では,この変化点検出戦略と楽観的アルゴリズムを組み合わせたロバストCPD-UCBを提案する。
論文 参考訳（メタデータ） (2025-05-26T14:40:47Z) - p-Mean Regret for Stochastic Bandits [52.828710025519996]
単純で統一された UCB ベースのアルゴリズムを導入し、新しい$p$-mean の後悔境界を実現する。
我々の枠組みは、特別な場合として、平均的な累積的後悔とナッシュ後悔の両方を包含する。
論文 参考訳（メタデータ） (2024-12-14T08:38:26Z) - Adaptive Smooth Non-Stationary Bandits [0.8158530638728501]
我々は、報酬がスムーズに変化する、$Kの非定常バンディットモデルについて研究する。
一般に、すべての$K,beta,lambda$に対してminimax動的後悔率を確立します。
また,非定常帯域におけるギャップ依存的後悔率の高速化についても検討した。
論文 参考訳（メタデータ） (2024-07-11T16:37:15Z) - A Unifying Framework for Online Optimization with Long-Term Constraints [62.35194099438855]
我々は,意思決定者が長期的制約の対象となる一連の意思決定をしなければならないオンライン学習問題について検討する。
目標は、全報酬を最大化し、同時に、$T$ラウンド全体で小さな累積違反を達成することである。
本稿では,この一般クラス問題に対して,未知のモデルに基づいて報酬と制約が選択された場合と,各ラウンドで敵が選択した場合の双方において,最良世界型アルゴリズムを提示する。
論文 参考訳（メタデータ） (2022-09-15T16:59:19Z) - Breaking the $\sqrt{T}$ Barrier: Instance-Independent Logarithmic Regret
in Stochastic Contextual Linear Bandits [10.127456032874978]
線形ペイオフを伴う文脈的包帯に対する対数的後悔(多元的後悔)を証明した。
コンテキストは、$sqrtT$から$polylog(T)$への後悔を減らすのに役立ちます。
論文 参考訳（メタデータ） (2022-05-19T23:41:46Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳（メタデータ） (2022-03-03T02:55:55Z) - An Experimental Design Approach for Regret Minimization in Logistic
Bandits [26.674062544226636]
ロジスティックな盗賊の最大の課題は、潜在的に大きな問題に依存する定数$kappa$への依存を減らすことである。
そこで本研究では,新しいウォームアップサンプリングアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-02-04T21:56:40Z) - Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning [56.23358327635815]
リプシッツ・バンディット(Lipschitz bandits)は、大規模で構造化された行動空間を研究する多腕バンディットの顕著なバージョンである。
ここでの中心的なテーマは、アクション空間の適応的な離散化であり、より有望な領域で徐々にズームインする'である。
逆バージョンにおける適応的な離散化のための最初のアルゴリズムを提供し、インスタンス依存の後悔境界を導出する。
論文 参考訳（メタデータ） (2020-06-22T16:06:25Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。