論文の概要: 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})$となる。 これらの値は、下限が全く知られていない特別な場合のすべての下限と一致し、よりよく研究された確率的問題に対して利用可能な最もよく知られた上限と一致する。

関連論文リスト

• Differential Privacy in Kernelized Contextual Bandits via Random Projections [8.658538065693206]
  コンテキストによるカーネルの帯域幅の問題について考察する。 基礎となる報酬関数は、既知の再生ケルネルヒルベルト空間に属する。 我々は、$widetildemathcalO(sqrtgamma_TT+fracgamma_Tvarepsilon_mathrmDP)の最先端の累積後悔を実現する新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-18T03:54:49Z)
• Dynamic Regret Reduces to Kernelized Static Regret [63.36965242404415]
  本研究では,オンライン凸最適化において,任意のベンチマークシーケンスに対して低累積損失を達成することを目的とした動的後悔について検討する。 再生ケルネルヒルベルト空間 (RKHS) の形で適切な関数空間を構築することにより、最適$R_T(u_1,ldots,u_T) = MathcalO(sqrtsum_t|u_t-u_t-1|T)$ dynamic regret guarantee。
  論文  参考訳（メタデータ） (2025-07-07T21:09:33Z)
• Multiclass Loss Geometry Matters for Generalization of Gradient Descent in Separable Classification [27.33243506775655]
  分離線形分類のための非正規化手法の一般化性能について検討する。 収束速度は損失テンプレートの幾何に大きく影響されていることを示す。
  論文  参考訳（メタデータ） (2025-05-28T13:39:14Z)
• Beyond Worst-Case Online Classification: VC-Based Regret Bounds for Relaxed Benchmarks [19.642496463491053]
  我々は、オンラインバイナリ分類を再考し、最良クラスのバイナリ損失との競合から、緩やかなベンチマークとの競合へと焦点を移した。 我々は、小さな入力摂動に対して頑健な予測器の比較、ガウス平滑化下での良好な性能、あるいは所定の出力マージンを維持することを検討する。 我々のアルゴリズムは、VC次元とインスタンス空間の複雑さにのみ依存する後悔の保証を達成する。
  論文  参考訳（メタデータ） (2025-04-14T18:00:23Z)
• Contextual Online Decision Making with Infinite-Dimensional Functional Regression [19.06054415343443]
  コンテキストシーケンシャルな意思決定問題は、機械学習において重要な役割を果たす。 我々は、あらゆる文脈のオンライン意思決定問題に対処するための普遍的な許容可能なアルゴリズムフレームワークを提供する。
  論文  参考訳（メタデータ） (2025-01-30T14:05:20Z)
• An Equivalence Between Static and Dynamic Regret Minimization [10.812831455376218]
  線形損失に対して、動的後悔最小化は、拡張決定空間における静的後悔最小化と等価であることを示す。 R_T(u_1,dots,u_T)le tildeという形式の動的後悔を保証するアルゴリズムを提供する。
  論文  参考訳（メタデータ） (2024-06-03T17:54:58Z)
• 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)
• Learning Adversarial Low-rank Markov Decision Processes with Unknown Transition and Full-information Feedback [30.23951525723659]
  本研究は,全情報フィードバック設定において,逆向きに損失が変化する低ランクMDPについて検討する。 政策最適化に基づくアルゴリズムPOLOを提案し、$widetildeO(Kfrac56Afrac12dln (1+M)/ (1-gamma)2)$ regret guarantee。
  論文  参考訳（メタデータ） (2023-11-14T03:12:43Z)
• 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)
• 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)
• Online nonparametric regression with Sobolev kernels [99.12817345416846]
  我々は、ソボレフ空間のクラス上の後悔の上限を$W_pbeta(mathcalX)$, $pgeq 2, beta>fracdp$ とする。 上界は minimax regret analysis で支えられ、$beta> fracd2$ または $p=infty$ の場合、これらの値は(本質的に)最適である。
  論文  参考訳（メタデータ） (2021-02-06T15:05:14Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。