論文の概要: Adversarial Contextual Bandits Go Kernelized
- arxiv url: http://arxiv.org/abs/2310.01609v1
- Date: Mon, 2 Oct 2023 19:59:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-10-04 18:56:21.180365
- Title: Adversarial Contextual Bandits Go Kernelized
- Title（参考訳）: 敵のコンテキストバンディットがカーネル化
- Authors: Gergely Neu, Julia Olkhovskaya, Sattar Vakili
- Abstract要約: 本研究では、ヒルベルト核空間に属する損失関数を組み込むことにより、逆線形文脈帯域におけるオンライン学習の問題を一般化する。
本稿では,損失関数を推定し,ほぼ最適の後悔の保証を再現するための新しい楽観的偏り推定器を提案する。
- 参考スコア（独自算出の注目度）: 21.007410990554522
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study a generalization of the problem of online learning in adversarial
linear contextual bandits by incorporating loss functions that belong to a
reproducing kernel Hilbert space, which allows for a more flexible modeling of
complex decision-making scenarios. We propose a computationally efficient
algorithm that makes use of a new optimistically biased estimator for the loss
functions and achieves near-optimal regret guarantees under a variety of
eigenvalue decay assumptions made on the underlying kernel. Specifically, under
the assumption of polynomial eigendecay with exponent $c>1$, the regret is
$\widetilde{O}(KT^{\frac{1}{2}(1+\frac{1}{c})})$, where $T$ denotes the number
of rounds and $K$ the number of actions. Furthermore, when the eigendecay
follows an exponential pattern, we achieve an even tighter regret bound of
$\widetilde{O}(\sqrt{T})$. These rates match the lower bounds in all special
cases where lower bounds are known at all, and match the best known upper
bounds available for the more well-studied stochastic counterpart of our
problem.
- Abstract（参考訳）: 本研究では,複雑な意思決定シナリオをより柔軟にモデル化できるカーネルヒルベルト空間に属する損失関数を組み込むことにより,逆線形文脈バンディットにおけるオンライン学習問題の一般化について検討する。
本稿では,損失関数に対する新しい楽観的に偏りのある推定器を用い,基礎となるカーネル上での固有値減衰仮定の多種多様さの下で,ほぼ最適の後悔保証を実現するアルゴリズムを提案する。
具体的には、多項式固有デカイと指数 $c>1$ の仮定の下で、後悔は$\widetilde{o}(kt^{\frac{1}{2}(1+\frac{1}{c})})$であり、ここで$t$はラウンド数、$k$はアクション数を表す。
さらに、固有デカイが指数的パターンに従うと、より厳密な後悔値が$\widetilde{o}(\sqrt{t})$となる。
これらの値は、下限が全く知られていない特別な場合のすべての下限と一致し、よりよく研究された確率的問題に対して利用可能な最もよく知られた上限と一致する。
関連論文リスト
- Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。
既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。
G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
論文 参考訳（メタデータ） (2024-01-14T14:14:19Z) - Refined Regret for Adversarial MDPs with Linear Function Approximation [50.00022394876222]
我々は,損失関数が約1,300ドル以上のエピソードに対して任意に変化するような,敵対的決定過程(MDP)の学習を検討する。
本稿では,同じ設定で$tildemathcal O(K2/3)$に対する後悔を改善する2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-01-30T14:37:21Z) - LegendreTron: Uprising Proper Multiclass Loss Learning [22.567234503869845]
損失関数は教師付き学習の基盤として機能し、しばしばモデル開発の前に選択される。
最近の研究は、損失とモデルを共同で引き起こそうとしている。
sc LegendreTron は,多クラス問題に対するアンフォプロペラの正準損失と確率を共同で学習する,新規かつ実用的な方法である。
論文 参考訳（メタデータ） (2023-01-27T13:10:45Z) - Parameter-free Regret in High Probability with Heavy Tails [45.11667443216861]
非有界領域に対するオンライン凸最適化のための新しいアルゴリズムを提案する。
高確率のパラメータフリーな後悔は、潜在的に重み付き下次推定にのみアクセス可能である。
論文 参考訳（メタデータ） (2022-10-25T21:43:44Z) - 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) - Optimal policy evaluation using kernel-based temporal difference methods [78.83926562536791]
カーネルヒルベルト空間を用いて、無限水平割引マルコフ報酬過程の値関数を推定する。
我々は、関連するカーネル演算子の固有値に明示的に依存した誤差の非漸近上界を導出する。
MRP のサブクラスに対する minimax の下位境界を証明する。
論文 参考訳（メタデータ） (2021-09-24T14:48:20Z) - High-probability Bounds for Non-Convex Stochastic Optimization with
Heavy Tails [55.561406656549686]
我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。
本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
論文 参考訳（メタデータ） (2021-06-28T00:17:01Z) - Localization, Convexity, and Star Aggregation [0.0]
オフセットラデマッハ複体は、正方形損失に対する鋭く線形依存的な上界を示すことが示されている。
統計的設定では、オフセット境界は一定の均一な凸性を満たす任意の損失に一般化可能であることを示す。
論文 参考訳（メタデータ） (2021-05-19T00:47:59Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。