論文の概要: No-Regret Linear Bandits under Gap-Adjusted Misspecification
- arxiv url: http://arxiv.org/abs/2501.05361v1
- Date: Thu, 09 Jan 2025 16:44:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-01-10 13:58:32.061959
- Title: No-Regret Linear Bandits under Gap-Adjusted Misspecification
- Title（参考訳）: ギャップ調整ミス種別下における非線形線形帯域
- Authors: Chong Liu, Dan Qiao, Ming Yin, Ilija Bogunovic, Yu-Xiang Wang,
- Abstract要約: 既存の線形包帯の作用は通常、最良の線形近似のsup-norm誤差を測定する一様不特定パラメータ$epsilon$に依存する。
そこで本研究では,各入力における近似誤差をx$で近似し,その差分をx$で比例する,より自然な不特定モデルを提案する。
我々は,従来のLinUCBアルゴリズムが,そのような$rho$-gap-adjusted misspecificationに対して自動的に堅牢であることを示す。
- 参考スコア（独自算出の注目度）: 38.592043705502725
- License:
- Abstract: This work studies linear bandits under a new notion of gap-adjusted misspecification and is an extension of Liu et al. (2023). When the underlying reward function is not linear, existing linear bandits work usually 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 propose 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 $\rho$-gap-adjusted misspecification with parameter $\rho$ diminishing at $O(1/(d \sqrt{\log T}))$. It achieves a near-optimal $O(\sqrt{T})$ regret for problems that the best-known regret is almost linear in time horizon $T$. We further advance this frontier by presenting a novel phased elimination-based algorithm whose gap-adjusted misspecification parameter $\rho = O(1/\sqrt{d})$ does not scale with $T$. This algorithm attains optimal $O(\sqrt{T})$ regret and is deployment-efficient, requiring only $\log T$ batches of exploration. It also enjoys an adaptive $O(\log T)$ regret when a constant suboptimality gap exists. Technically, our proof relies on a novel self-bounding argument that bounds the part of the regret due to misspecification by the regret itself, and a new inductive lemma that limits the misspecification error within the suboptimality gap for all valid actions in each batch selected by G-optimal design.
- Abstract（参考訳）: この研究は、ギャップ調整された不特定性という新しい概念の下で線形帯域について研究し、Liu et al (2023) の拡張である。
基礎となる報酬関数が線型でないとき、既存の線形包帯の作用は通常、最良の線形近似のsup-norm誤差を測定する一様不特定パラメータ $\epsilon$ に依存する。
これにより$\epsilon > 0$ となると、避けられない線形後悔が発生する。
そこで本研究では,各入力における近似誤差をx$で近似し,その差分をx$で比例する,より自然なミス種別モデルを提案する。
これは、最適化問題に対して、近最適領域がより重要であり、準最適領域におけるより大きな近似誤差を許容できるという直感を捉えている。
驚くほど驚くべきことに、古典的なLinUCBアルゴリズムは、実現可能なケースのために設計されており、パラメータ$\rho$-gap調整ミススペクテーションを$O(1/(d \sqrt{\log T})$で減少させるような$\rho$-adjustedのミススペクテーションに対して、自動的に堅牢である。
ほぼ最適の$O(\sqrt{T})$後悔を達成し、最もよく知られた後悔は時間的地平線においてほぼ線形である。
我々は、このフロンティアをさらに前進させ、ギャップ調整された不特定パラメータ $\rho = O(1/\sqrt{d})$ が$T$ でスケールしないような、新しい位相除去アルゴリズムを提示する。
このアルゴリズムは、最適な$O(\sqrt{T})$後悔し、デプロイ効率が高く、探索のバッチに$\log T$しか必要としない。
また、一定の準最適差が存在する場合、適応的な$O(\log T)$後悔も楽しめる。
技術的には、この証明は、後悔そのものによる不特定性による後悔の一部を束縛する新しい自己拘束的議論と、G-最適設計によって選択された各バッチにおけるすべての有効なアクションに対して、最適以下のギャップ内の不特定性エラーを制限する新しい帰納的補題に依拠する。
関連論文リスト
- Misspecified $Q$-Learning with Sparse Linear Function Approximation: Tight Bounds on Approximation Error [25.777423855881878]
我々は、$Oleft(Hepsilonright)$-optimal Policyを得ることができることを示す新しい除去アルゴリズムを示す。
我々は上界を$widetildeOmegaleft(Hepsilonright)$-optimality lower boundで補い、この問題の完全な図面を与える。
論文 参考訳（メタデータ） (2024-07-18T15:58:04Z) - LC-Tsallis-INF: Generalized Best-of-Both-Worlds Linear Contextual Bandits [38.41164102066483]
本研究では、独立かつ同一に分散したコンテキストを持つ線形文脈帯域問題について考察する。
提案アルゴリズムは、Tsallisエントロピーを持つFollow-The-Regularized-Leaderに基づいており、$alpha$-textual-Con (LC)-Tsallis-INFと呼ばれている。
論文 参考訳（メタデータ） (2024-03-05T18:59:47Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳（メタデータ） (2024-02-14T07:52:00Z) - On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits [76.2262680277608]
本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。
このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
論文 参考訳（メタデータ） (2023-03-16T15:24:29Z) - No-Regret Linear Bandits beyond Realizability [34.06789803260447]
報酬関数が線形でない場合の線形帯域について検討する。
既存の作業は、最良の線形近似のsup-norm誤差を測定する均一な不特定パラメータ$epsilon$に依存している。
ここでは、各入力においてx$の近似誤差のみを必要とし、x$の準最適差に比例する、より自然なミス種別モデルを記述する。
論文 参考訳（メタデータ） (2023-02-26T07:15:31Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Private Stochastic Convex Optimization: Optimal Rates in $\ell_1$
Geometry [69.24618367447101]
対数要因まで $(varepsilon,delta)$-differently private の最適過剰人口損失は $sqrtlog(d)/n + sqrtd/varepsilon n.$ です。
損失関数がさらなる滑らかさの仮定を満たすとき、余剰損失は$sqrtlog(d)/n + (log(d)/varepsilon n)2/3で上界(対数因子まで)であることが示される。
論文 参考訳（メタデータ） (2021-03-02T06:53:44Z) - Optimal Regret Algorithm for Pseudo-1d Bandit Convex Optimization [51.23789922123412]
我々は,バンディットフィードバックを用いてオンライン学習を学習する。
learnerは、コスト/リワード関数が"pseudo-1d"構造を許可するゼロ次オラクルのみにアクセスできる。
我々は、$T$がラウンドの数である任意のアルゴリズムの後悔のために$min(sqrtdT、T3/4)$の下限を示しています。
ランダム化オンライングラデーション下降とカーネル化指数重み法を組み合わせた新しいアルゴリズムsbcalgを提案し,疑似-1d構造を効果的に活用する。
論文 参考訳（メタデータ） (2021-02-15T08:16:51Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。