論文の概要: Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
- arxiv url: http://arxiv.org/abs/2010.12642v2
- Date: Tue, 9 Mar 2021 11:09:05 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-03 21:59:44.876792
- Title: Instance-Wise Minimax-Optimal Algorithms for Logistic Bandits
- Title（参考訳）: ロジスティックバンディットのインスタンスワイズミニマックス最適アルゴリズム
- Authors: Marc Abeille, Louis Faury and Cl\'ement Calauz\`enes
- Abstract要約: ロジスティック・バンディットは、パラメタライズド・バンディットにおける非線形性の影響を理解するための、散らかったが挑戦的な枠組みを提供することによって、かなりの注目を集めている。
非線型性の効果を精密に解析する新しいアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 9.833844886421694
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Logistic Bandits have recently attracted substantial attention, by providing
an uncluttered yet challenging framework for understanding the impact of
non-linearity in parametrized bandits. It was shown by Faury et al. (2020) that
the learning-theoretic difficulties of Logistic Bandits can be embodied by a
large (sometimes prohibitively) problem-dependent constant $\kappa$,
characterizing the magnitude of the reward's non-linearity. In this paper we
introduce a novel algorithm for which we provide a refined analysis. This
allows for a better characterization of the effect of non-linearity and yields
improved problem-dependent guarantees. In most favorable cases this leads to a
regret upper-bound scaling as $\tilde{\mathcal{O}}(d\sqrt{T/\kappa})$, which
dramatically improves over the $\tilde{\mathcal{O}}(d\sqrt{T}+\kappa)$
state-of-the-art guarantees. We prove that this rate is minimax-optimal by
deriving a $\Omega(d\sqrt{T/\kappa})$ problem-dependent lower-bound. Our
analysis identifies two regimes (permanent and transitory) of the regret, which
ultimately re-conciliates Faury et al. (2020) with the Bayesian approach of
Dong et al. (2019). In contrast to previous works, we find that in the
permanent regime non-linearity can dramatically ease the
exploration-exploitation trade-off. While it also impacts the length of the
transitory phase in a problem-dependent fashion, we show that this impact is
mild in most reasonable configurations.
- Abstract（参考訳）: ロジスティック・バンディットは、パラメトリッド・バンディットにおける非線形性の影響を理解するための議論の余地のない挑戦的な枠組みを提供することで、近年注目を集めている。
Faury et al. (2020) は、ロジスティック・バンドの学習理論上の困難さは、報酬の非線型性の大きさを特徴づける問題依存定数 $\kappa$ によって具体化できることを示した。
本稿では,洗練された解析を行う新しいアルゴリズムを提案する。
これにより、非線形性の影響をよりよくキャラクタリゼーションすることができ、問題依存の保証を改善することができる。
ほとんどの好例では、これは、$\tilde{\mathcal{O}}(d\sqrt{T/\kappa})$として残念な上限スケーリングをもたらし、$\tilde{\mathcal{O}}(d\sqrt{T}+\kappa)$ state-of-the-art guaranteesよりも劇的に改善される。
このレートは、$\omega(d\sqrt{t/\kappa})$問題依存低バウンドを導出することでミニマックス最適であることが証明される。
本分析では、後悔の2つのレジーム(永久的および過渡的)を特定し、最終的にfauly et al. (2020) と dong et al. (2019) のベイズ的アプローチを両立させた。
従来の研究とは対照的に、永続的な体制では、非線形性は探査・探査のトレードオフを劇的に緩和することができる。
問題依存的な方法で遷移相の長さにも影響するが、ほとんどの合理的な構成では、この影響は軽度である。
関連論文リスト
- Improved Bound for Robust Causal Bandits with Linear Models [16.60875994745622]
本稿では,時間的モデル変動に直面した因果包帯のロバスト性について検討する。
提案アルゴリズムは,$C$が$o(sqrtT)$の場合に,ほぼ最適な$tildemathcalO(sqrtT)$後悔を達成する。
論文 参考訳（メタデータ） (2024-05-13T14:41:28Z) - Settling the Sample Complexity of Online Reinforcement Learning [92.02082223856479]
バーンインコストを発生させることなく、最小限の最適後悔を実現する方法を示す。
最適値/コストや一定の分散といった問題依存量の影響を明らかにするために、我々の理論を拡張します。
論文 参考訳（メタデータ） (2023-07-25T15:42:11Z) - Revisiting Weighted Strategy for Non-stationary Parametric Bandits [82.1942459195896]
本稿では,非定常パラメトリックバンディットの重み付け戦略を再考する。
より単純な重みに基づくアルゴリズムを生成する改良された分析フレームワークを提案する。
我々の新しいフレームワークは、他のパラメトリックバンディットの後悔の限界を改善するのに使える。
論文 参考訳（メタデータ） (2023-03-05T15:11:14Z) - Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement
Learning: Adaptivity and Computational Efficiency [90.40062452292091]
本稿では,不整合雑音を持つ線形帯域に対する計算効率のよい最初のアルゴリズムを提案する。
我々のアルゴリズムは未知のノイズの分散に適応し、$tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regretを達成する。
また、強化学習において、線形混合マルコフ決定過程(MDP)に対する分散適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-02-21T00:17:24Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳（メタデータ） (2022-07-23T20:25:07Z) - Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。
時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。
また, 動的上界に依存した新しい行列不等式濃度を証明した。
論文 参考訳（メタデータ） (2021-10-15T12:32:33Z) - Non-stationary Linear Bandits Revisited [26.082923174615495]
非定常線形帯域は、時間変化の根底にある回帰パラメータを持つ線形帯域の変種である。
これらのアルゴリズムに対して,$widetildeO(T3/4(1+P_T)1/4)$ dynamic regretを証明した。
論文 参考訳（メタデータ） (2021-03-09T10:07:17Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳（メタデータ） (2020-09-04T04:10:39Z) - Improved Optimistic Algorithms for Logistic Bandits [16.140301473601454]
そこで本稿では,報酬関数の非線形性について,より詳細な検証に基づく新しい楽観的アルゴリズムを提案する。
我々は、$tildemathcalO(sqrtT)$ regretを楽しんでおり、$kappa$に依存しないが、第2の順序の項には依存しないことを示す。
論文 参考訳（メタデータ） (2020-02-18T12:52:32Z) - Contextual Linear Bandits under Noisy Features: Towards Bayesian Oracles [65.9694455739978]
特徴不確実性の下での文脈線形帯域問題について検討する。
本分析により, 最適仮説は, 雑音特性に応じて, 基礎となる実現可能性関数から著しく逸脱しうることが明らかとなった。
これは、古典的アプローチが非自明な後悔境界を保証できないことを意味する。
論文 参考訳（メタデータ） (2017-03-03T21:39:56Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。