論文の概要: Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits
- arxiv url: http://arxiv.org/abs/2611.12140v2
- Date: Wed, 11 Nov 2026 17:03:18 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-14 01:36:32.884436
- Title: Visible Tails: Characterizing Adaptation to Unknown Moments in Heavy-Tailed Bandits
- Title(参考訳): バイシブル・タイル:ヘビータイルバンドにおける未知のモーメントへの適応を特徴付ける
- Abstract要約: 最適報酬法に基づく片側視認性条件の尺度による障害の特徴付けを行う。
可視性定数が与えられた量子トリミング UCB 指数は、各指数において腕固有のモーメントレートを達成する。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Heavy-tailed bandit learners must tell a poor arm from an arm whose favorable rewards have not yet appeared. We characterize this obstruction through a scale of one-sided visibility conditions on the optimal reward law: the mean hidden in a rare event is at most a constant multiple of a retained central moment. A quantile-trimmed UCB index that is given the visibility constants attains arm-specific moment rates at every exponent, with no lower bound on the exponent. Conversely, every strategy with a fixed exploration budget has polynomial regret on each law that violates the corresponding condition. For the variance benchmark we determine the order of both budget constants in the visibility level. The frontier depends on the largest exponent the benchmark promises, and the resulting classes are strictly nested. The same index has logarithmic expected regret when rewards are integrable, with a coefficient that can be exponential in the inverse gap.
- Abstract(参考訳): ヘビーテールのバンディット学習者は、好意的な報酬がまだ現れていない腕から貧しい腕に伝えなければならない。
我々は、この障害を、最適報酬法に基づく片側視認性条件の尺度により特徴づける:まれな事象に隠れた平均は、保持された中心モーメントの少なくとも1つの一定倍である。
可視性定数が与えられた量子トリミング UCB 指数は、指数に下限を持たず、各指数で腕固有のモーメントレートを達成する。
逆に、固定的な調査予算を持つ全ての戦略は、対応する条件に反する各法則に対して、多項式的後悔を持つ。
分散ベンチマークでは、両予算定数の順序を可視度で決定する。
フロンティアはベンチマークが約束する最大の指数に依存し、その結果のクラスは厳密にネストされる。
同じ指数は、報酬が可積分であるときに対数的に期待される後悔を持ち、逆ギャップで指数関数的な係数を持つ。
関連論文リスト
- Variance-Aware Non-Stationary Bandits:All-Budget Regret Bounds and Adaptation Costs [1.469272550839244]
低報酬分散は推定コストを低減させるが、観測されていないまま改善される可能性のある腕の監視を排除しない。
我々は,2つのコストが,有界,非定常なマルチ武器帯における供給されるばらつきと変動予算にどのように依存するかを特徴付ける。
論文 参考訳(メタデータ) (2026-10-19T10:10:27Z) - Transfer Learning in Bandits from Unknown Adaptive Policies: Problem-Dependent Lower and Upper Bounds [5.617291981476444]
我々は,有界報酬を$[0,1]$で伝達学習する手法について検討する。
オンラインゲームが始まる前に、学習者は各アームの$k$、$N'_k$の観察をi.i.d.で受け取る。
対数的後悔は、改善から劣化した対数的障害、保証の喪失までの3つの条件を特徴付けることで、不特定の下で生き残ることができることを示す。
論文 参考訳(メタデータ) (2026-10-15T09:30:13Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳(メタデータ) (2026-09-07T01:38:41Z) - Quick Change Detection in Discrete-Time in Presence of a Covert Adversary [7.58317340007754]
離散時間における最短変動検出の問題について検討し, 観測結果の列が未知の時間で分布変化を行う場合について検討する。
平均検出遅延 (ADD) と, 後変化分布が前変化分布に収束した場合の平均誤報 (AT2FA) の挙動を, $to infty$として特徴づける。
ADD = $()$ と定義されているが、古典的な設定では ADD は $ としてしか成長しない。
論文 参考訳(メタデータ) (2026-01-27T19:56:31Z) - Continuous K-Max Bandits [54.21533414838677]
我々は、連続的な結果分布と弱い値-インデックスフィードバックを持つ、$K$-Maxのマルチアームバンディット問題について検討する。
この設定は、レコメンデーションシステム、分散コンピューティング、サーバスケジューリングなどにおいて重要なアプリケーションをキャプチャします。
我々の重要な貢献は、適応的な離散化とバイアス補正された信頼境界を組み合わせた計算効率の良いアルゴリズムDCK-UCBである。
論文 参考訳(メタデータ) (2025-02-19T06:37:37Z) - Variance-Aware Regret Bounds for Stochastic Contextual Dueling Bandits [53.281230333364505]
本稿では, 一般化線形モデル(GLM)から, デュエルアームのバイナリ比較を生成するコンテキストデュエルバンド問題について検討する。
本稿では,SupLinUCB型アルゴリズムを提案する。このアルゴリズムは,計算効率と分散を意識したリセットバウンド$tilde Obig(dsqrtsum_t=1Tsigma_t2 + dbig)$を提案する。
我々の後悔は、比較が決定論的である場合の直感的な期待と自然に一致し、アルゴリズムは$tilde O(d)$ regretにのみ悩まされる。
論文 参考訳(メタデータ) (2023-10-02T08:15:52Z) - The Best of Both Worlds: Reinforcement Learning with Logarithmic Regret
and Policy Switches [84.54669549718075]
漸進的強化学習(RL)における後悔の最小化問題について検討する。
一般関数クラスと一般モデルクラスで学ぶことに集中する。
対数的後悔境界は$O(log T)$スイッチングコストのアルゴリズムによって実現可能であることを示す。
論文 参考訳(メタデータ) (2022-03-03T02:55:55Z) - A New Look at Dynamic Regret for Non-Stationary Stochastic Bandits [11.918230810566945]
本研究では,学習過程において各腕の報酬統計が数回変化しうる非定常的マルチアームバンディット問題について検討する。
我々は、$K$の武器付きバンディット問題において、ほぼ最適の$widetilde O(sqrtK N(S+1))$ dynamic regretを実現する方法を提案する。
論文 参考訳(メタデータ) (2022-01-17T17:23:56Z) - Low-Complexity Algorithm for Restless Bandits with Imperfect Observations [1.4542411354617986]
我々は、強化学習と最適化において幅広い応用分野を見出す、レスレス・バンディット問題の一類を考察する。
我々は,観測誤差を伴う一般的なレスト・バンディット・モデルに容易に適用可能な,高い性能を実現する低複雑性アルゴリズムを開発した。
論文 参考訳(メタデータ) (2021-08-09T05:01:19Z) - Stochastic Linear Bandits Robust to Adversarial Attacks [117.665995707568]
我々はロバスト位相除去アルゴリズムの2つの変種を提供し、その1つは$C$を知っており、もう1つはそうでない。
いずれの変種も、倒壊しない場合には、それぞれ$C = 0$ となり、それぞれ追加の加法項が生じる。
文脈的設定では、単純な欲求的アルゴリズムは、明示的な探索を行わず、C$を知らないにもかかわらず、ほぼ最適加法的後悔項で証明可能な堅牢性を示す。
論文 参考訳(メタデータ) (2020-07-07T09:00:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。