論文の概要: On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits
- arxiv url: http://arxiv.org/abs/2303.09390v1
- Date: Thu, 16 Mar 2023 15:24:29 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-17 15:06:05.558886
- Title: On the Interplay Between Misspecification and Sub-optimality Gap in
Linear Contextual Bandits
- Title（参考訳）: リニアコンテクストバンディットにおけるミス種別とサブオプティマスギャップの相互作用について
- Authors: Weitong Zhang and Jiafan He and Zhiyuan Fan and Quanquan Gu
- Abstract要約: 本研究では,線形関数クラスによって期待される報酬関数を近似できるような,不特定条件下での線形文脈帯域について検討する。
このアルゴリズムは, 対数的因子に比例した設定において, ギャップ依存の残差が$tilde O (d2/Delta)$と同じであることを示す。
- 参考スコア（独自算出の注目度）: 76.2262680277608
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study linear contextual bandits in the misspecified setting, where the
expected reward function can be approximated by a linear function class up to a
bounded misspecification level $\zeta>0$. We propose an algorithm based on a
novel data selection scheme, which only selects the contextual vectors with
large uncertainty for online regression. We show that, when the
misspecification level $\zeta$ is dominated by $\tilde O (\Delta / \sqrt{d})$
with $\Delta$ being the minimal sub-optimality gap and $d$ being the dimension
of the contextual vectors, our algorithm enjoys the same gap-dependent regret
bound $\tilde O (d^2/\Delta)$ as in the well-specified setting up to
logarithmic factors. In addition, we show that an existing algorithm SupLinUCB
(Chu et al., 2011) can also achieve a gap-dependent constant regret bound
without the knowledge of sub-optimality gap $\Delta$. Together with a lower
bound adapted from Lattimore et al. (2020), our result suggests an interplay
between misspecification level and the sub-optimality gap: (1) the linear
contextual bandit model is efficiently learnable when $\zeta \leq \tilde
O(\Delta / \sqrt{d})$; and (2) it is not efficiently learnable when $\zeta \geq
\tilde \Omega({\Delta} / {\sqrt{d}})$. Experiments on both synthetic and
real-world datasets corroborate our theoretical results.
- Abstract（参考訳）: 本研究では,不特定設定における線形文脈バンディットについて検討し,期待報酬関数は境界的不特定化レベル$\zeta>0$までの線形関数クラスで近似できることを示した。
本稿では,オンライン回帰の不確実性が大きい文脈ベクトルのみを選択する新しいデータ選択方式に基づくアルゴリズムを提案する。
誤特定レベル $\zeta$ が$\tilde o (\delta / \sqrt{d})$ で、$\delta$ が最小の準最適ギャップであり、$d$ が文脈ベクトルの次元であるとき、アルゴリズムは$\tilde o (d^2/\delta)$ が対数因子に設定されるのと同じギャップ依存の後悔を楽しむ。
さらに,既存のアルゴリズムであるSupLinUCB (Chu et al., 2011) が,準最適ギャップ$\Delta$の知識を必要とせずに,ギャップ依存の連続後悔境界を達成可能であることを示す。
Lattimore et al. (2020) より適応された下限とともに、この結果は、(1) 線形文脈的帯域幅モデルは、$\zeta \leq \tilde O(\Delta / \sqrt{d})$, (2) が$\zeta \geq \tilde \Omega({\Delta} / {\sqrt{d}})$の場合に効率よく学習可能であることを示唆している。
合成と実世界の両方のデータセットの実験は、我々の理論的結果を裏付ける。
関連論文リスト
- 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) - Best Policy Identification in Linear MDPs [70.57916977441262]
縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。
複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
論文 参考訳（メタデータ） (2022-08-11T04:12:50Z) - Nearly Minimax Optimal Reinforcement Learning with Linear Function
Approximation [25.60689712525918]
本稿では,遷移確率と報酬関数が線形な線形関数近似を用いた強化学習について検討する。
本稿では,新たなアルゴリズムLSVI-UCB$+$を提案し,$H$がエピソード長,$d$が特徴次元,$T$がステップ数である場合に,$widetildeO(HdsqrtT)$ regretboundを実現する。
論文 参考訳（メタデータ） (2022-06-23T06:04:21Z) - Fine-Grained Gap-Dependent Bounds for Tabular MDPs via Adaptive
Multi-Step Bootstrap [84.66885506098724]
本稿では,アダプティブ・マルチステップ・ブートストラップ (AMB) を用いた表層有限水平マルコフ決定過程 (MDP) のモデルフリーアルゴリズムを提案する。
AMBは,部分最適ギャップの逆の和でのみスケールする,ギャップ依存的後悔境界を達成できることを示す。
また、AMB は $frac|Z_mul|Delta_min$ regret という追加の $frac|Z_mul|Delta_min$ を被っていることも示しています。
論文 参考訳（メタデータ） (2021-02-09T07:46:34Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-20T04:29:18Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov
Decision Processes [91.38793800392108]
本稿では,マルコフ決定過程(MDP)の遷移確率核が線形混合モデルである線形関数近似による強化学習について検討する。
上記の線形混合 MDP に対して$textUCRL-VTR+$ という線形関数近似を用いた計算効率の良い新しいアルゴリズムを提案する。
我々の知る限り、これらは線形関数近似を持つRLのための計算効率が良く、ほぼ最小のアルゴリズムである。
論文 参考訳（メタデータ） (2020-12-15T18:56:46Z) - Smooth Bandit Optimization: Generalization to H\"older Space [37.15553727896912]
我々は、目標が累積後悔である滑らかな報酬関数のバンディット最適化を考える。
私たちの主な結果は、指数 $alpha>1$ を持つ H"older space への報酬関数の一般化です。
私たちは、$alphaleq 1$サブセット内で、既存の下限に適合する後悔率を達成することを示します。
論文 参考訳（メタデータ） (2020-12-11T01:43:25Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。