論文の概要: No-Regret Linear Bandits beyond Realizability

• arxiv url: http://arxiv.org/abs/2302.13252v2
• Date: Wed, 19 Jul 2023 23:05:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-21 18:28:13.562484
• Title: No-Regret Linear Bandits beyond Realizability
• Title（参考訳）: 実現可能性を超えたノンレグレット線形バンディット
• Authors: Chong Liu, Ming Yin, Yu-Xiang Wang
• Abstract要約: 報酬関数が線形でない場合の線形帯域について検討する。 既存の作業は、最良の線形近似のsup-norm誤差を測定する均一な不特定パラメータ$epsilon$に依存している。 ここでは、各入力においてx$の近似誤差のみを必要とし、x$の準最適差に比例する、より自然なミス種別モデルを記述する。
• 参考スコア（独自算出の注目度）: 34.06789803260447
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study linear bandits when the underlying reward function is not linear. Existing work relies on a uniform misspecification parameter $\epsilon$ that measures the sup-norm error of the best linear approximation. This results in an unavoidable linear regret whenever $\epsilon > 0$. We describe a more natural model of misspecification which only requires the approximation error at each input $x$ to be proportional to the suboptimality gap at $x$. It captures the intuition that, for optimization problems, near-optimal regions should matter more and we can tolerate larger approximation errors in suboptimal regions. Quite surprisingly, we show that the classical LinUCB algorithm -- designed for the realizable case -- is automatically robust against such gap-adjusted misspecification. It achieves a near-optimal $\sqrt{T}$ regret for problems that the best-known regret is almost linear in time horizon $T$. Technically, our proof relies on a novel self-bounding argument that bounds the part of the regret due to misspecification by the regret itself.
• Abstract（参考訳）: 報酬関数が線形でない場合の線形帯域について検討する。 既存の仕事は、最良線形近似の超ノルム誤差を測定する一様不特定化パラメータ$\epsilon$に依存している。 これにより、$\epsilon > 0$ となると、避けられない線形後悔となる。 ここでは、各入力においてx$の近似誤差のみを必要とし、x$の準最適差に比例する、より自然なミス種別モデルを記述する。 最適化問題に対して、近最適領域はより重要であり、準最適領域におけるより大きな近似誤差を許容できるという直感を捉える。 驚くほど驚くべきことに、古典的なLinUCBアルゴリズムは、実現可能なケースのために設計されており、このようなギャップ調整ミスセグメンテーションに対して自動的に堅牢である。 最もよく知られた後悔は、time horizon $t$でほぼ線形である問題に対して、ほぼ最適の$\sqrt{t}$ regretが得られる。 技術的には、我々の証明は、後悔そのものによる不特定性による後悔の一部を束縛する、新しい自己拘束的議論に依存している。

関連論文リスト

• Tangential Randomization in Linear Bandits (TRAiL): Guaranteed Inference and Regret Bounds [1.03590082373586]
  本稿では,線形帯域探索アルゴリズムTRAiLの提案と解析を行う。 TraiLは、設計(回帰器)行列の最小固有値によって測定された推論品質の$Omega(sqrtT)$成長を保証する。 我々は,期待された後悔に対して,任意のアルゴリズムに対して$Omega(sqrtT)$ minimax小境界を特徴付ける。
  論文  参考訳（メタデータ） (2024-11-19T01:08:13Z)
• Rate-Preserving Reductions for Blackwell Approachability [72.03309261614991]
  Abernethy et al. (2011) はブラックウェルのアプローチ可能性と非回帰学習が等価であることを示した。 一般化された後悔最小化の例に対して、いかなるアプローチ可能性のインスタンスも厳格に削減できることが示される。
  論文  参考訳（メタデータ） (2024-06-10T23:23:52Z)
• Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic Shortest Path [80.60592344361073]
  線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。 エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。 既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
  論文  参考訳（メタデータ） (2024-02-14T07:52:00Z)
• $(\epsilon, u)$-Adaptive Regret Minimization in Heavy-Tailed Bandits [29.966828248335972]
  我々は,学習者に対して,$epsilon$と$u$が不明な場合に,後悔の最小化問題を調査する。 AdaR-UCBは、適応しない重みを帯びたケースとほぼ一致した後悔の保証を享受する最初のアルゴリズムである。
  論文  参考訳（メタデータ） (2023-10-04T17:11:15Z)
• On the Interplay Between Misspecification and Sub-optimality Gap in Linear Contextual Bandits [76.2262680277608]
  本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。 このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
  論文  参考訳（メタデータ） (2023-03-16T15:24:29Z)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  我々は、高次元 $ell_infty$-approachability 問題を、低次元の擬ノルムアプローチ可能性問題に変換する。 我々は、$ell$や他のノルムに対するアプローチ可能性に関する以前の研究に類似した疑似ノルムアプローチ可能性のアルゴリズム理論を開発する。
  論文  参考訳（メタデータ） (2023-02-03T03:19:14Z)
• First-Order Regret in Reinforcement Learning with Linear Function Approximation: A Robust Estimation Approach [57.570201404222935]
  我々は,大規模状態空間を用いた強化学習において,$mathcalO(sqrtV_1star K)$として,後悔のスケーリングが得られることを示す。 この結果を得るためには,少なくとも2乗推定に基づく既存手法は不十分であることを示す。
  論文  参考訳（メタデータ） (2021-12-07T00:29:57Z)
• Almost Optimal Batch-Regret Tradeoff for Batch Linear Contextual Bandits [45.43968161616453]
  バッチ線形文脈帯域に対する最適バッチ-regretトレードオフについて検討する。 時間的地平線が成長するにつれて2相表現を特徴とする後悔の保証を証明します。 また, 動的上界に依存した新しい行列不等式濃度を証明した。
  論文  参考訳（メタデータ） (2021-10-15T12:32:33Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits [13.32560004325655]
  古典的な$K$武器の線形文脈包帯問題の逆変法を考える。 $d$-dimensionalコンテキストがランダムに生成されるという仮定の下で、古典的なExp3アルゴリズムに基づいて効率的なアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2020-02-01T22:49:46Z)

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

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