論文の概要: Does Sparsity Help in Learning Misspecified Linear Bandits?
- arxiv url: http://arxiv.org/abs/2303.16998v1
- Date: Wed, 29 Mar 2023 19:58:39 GMT
- ステータス: 処理完了
- システム内更新日: 2023-03-31 15:11:30.367123
- Title: Does Sparsity Help in Learning Misspecified Linear Bandits?
- Title(参考訳): 空間性は不特定線形帯域学習に役立つか?
- Authors: Jialin Dong and Lin F. Yang
- Abstract要約: アルゴリズムは$O(varepsilon-sds)$アクションをクエリすることで、$O(varepsilon)$-optimalアクションを得ることができることを示す。
また、サンプルの複雑さに対する上限は、エラーが$O(sdeltavarepsilon)$$$0delta1$を要求する場合、ほぼ厳密であることを示す。
- 参考スコア(独自算出の注目度): 32.920577630673804
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Recently, the study of linear misspecified bandits has generated intriguing
implications of the hardness of learning in bandits and reinforcement learning
(RL). In particular, Du et al. (2020) show that even if a learner is given
linear features in $\mathbb{R}^d$ that approximate the rewards in a bandit or
RL with a uniform error of $\varepsilon$, searching for an
$O(\varepsilon)$-optimal action requires pulling at least $\Omega(\exp(d))$
queries. Furthermore, Lattimore et al. (2020) show that a degraded
$O(\varepsilon\sqrt{d})$-optimal solution can be learned within
$\operatorname{poly}(d/\varepsilon)$ queries. Yet it is unknown whether a
structural assumption on the ground-truth parameter, such as sparsity, could
break the $\varepsilon\sqrt{d}$ barrier. In this paper, we address this
question by showing that algorithms can obtain $O(\varepsilon)$-optimal actions
by querying $O(\varepsilon^{-s}d^s)$ actions, where $s$ is the sparsity
parameter, removing the $\exp(d)$-dependence. We then establish
information-theoretical lower bounds, i.e., $\Omega(\exp(s))$, to show that our
upper bound on sample complexity is nearly tight if one demands an error $
O(s^{\delta}\varepsilon)$ for $0<\delta<1$. For $\delta\geq 1$, we further show
that $\operatorname{poly}(s/\varepsilon)$ queries are possible when the linear
features are "good" and even in general settings. These results provide a
nearly complete picture of how sparsity can help in misspecified bandit
learning and provide a deeper understanding of when linear features are
"useful" for bandit and reinforcement learning with misspecification.
- Abstract(参考訳): 近年、線形不特定化バンディットの研究は、バンディットと強化学習(rl)における学習の難しさの興味深い影響を生み出している。
特に、du et al. (2020) は、たとえ学習者がバンドイットやrlの報酬を近似する$\mathbb{r}^d$ の線形特徴を与えられたとしても、$\varepsilon$ という一様誤差で、$o(\varepsilon)$-optimal なアクションを探索するには少なくとも $\omega(\exp(d))$ クエリを引く必要があることを示した。
さらに lattimore et al. (2020) は、分解された $o(\varepsilon\sqrt{d})$-optimal solution が $\operatorname{poly}(d/\varepsilon)$ クエリで学習可能であることを示した。
しかし、空間性のような基底構造パラメータの構造的仮定が$\varepsilon\sqrt{d}$障壁を破るかどうかは不明である。
本稿では、アルゴリズムが$o(\varepsilon^{-s}d^s)$アクションをクエリすることで、$o(\varepsilon)$-optimalアクションを得ることができることを示すことで、この問題に対処する。
次に、情報理論的な下限、すなわち$\omega(\exp(s))$を定め、もし誤差$ o(s^{\delta}\varepsilon)$ が$0<\delta<1$ であるなら、サンプル複雑性の上限がほぼタイトであることを示す。
また、$\delta\geq 1$に対して、線形な機能が"良い"ときや一般的な設定でも$\operatorname{poly}(s/\varepsilon)$クエリが可能であることをさらに示します。
これらの結果は,不特定バンディット学習において空間性がいかに有効であるかを概観し,不特定バンディット学習や強化学習において線形特徴がいつ有用であるかをより深く理解する。
関連論文リスト
- Almost Minimax Optimal Best Arm Identification in Piecewise Stationary Linear Bandits [55.957560311008926]
そこで本研究では,各文脈の平均値によって腕の質を計測するPSLBモデルを提案する。
PS$varepsilon$BAI$+$は、$varepsilon$-optimal armを、確率$ge 1-delta$と最小限のサンプルで識別することが保証される。
論文 参考訳(メタデータ) (2024-10-10T06:15:42Z) - 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) - Fast Rates for Bandit PAC Multiclass Classification [73.17969992976501]
我々は,帯域幅フィードバックを用いたマルチクラスPAC学習について検討し,入力を$K$ラベルの1つに分類し,予測されたラベルが正しいか否かに制限する。
我々の主な貢献は、問題の無知な$(varepsilon,delta)$PACバージョンのための新しい学習アルゴリズムを設計することである。
論文 参考訳(メタデータ) (2024-06-18T08:54:04Z) - Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
サイズ $tilde O(varepsilon-2d)$ for $p2$ と $tilde O(varepsilon-pdp/2)$ for $p>2$ のコアセットを構築します。
1p2$の場合、すべての行列は$tilde O(varepsilon-1k)$行のサブセットを持ち、$(varepsilon-1k)$-a optimal $k$-dimensional subspace for $ell_p$ subspace approximationである。
論文 参考訳(メタデータ) (2024-06-04T15:50:42Z) - On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
本研究は,学習者によって達成可能な最小のエラー$epsilon=epsilon(eta)$を,そのような敵の存在下で特徴付けることを目的とする。
注目すべきは,上界が決定論的学習者によって達成できることである。
論文 参考訳(メタデータ) (2022-10-06T06:49:48Z) - Tractability from overparametrization: The example of the negative
perceptron [9.077560551700163]
我々は線形プログラミングアルゴリズムを解析し、対応するしきい値である$delta_textlin(kappa)$を特徴付ける。
閾値$delta_textlin(kappa)$間のギャップを観察し、他のアルゴリズムの振る舞いに関する疑問を提起する。
論文 参考訳(メタデータ) (2021-10-28T01:00:13Z) - The Price of Tolerance in Distribution Testing [31.10049510641336]
サンプルの複雑さは [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2 であることが示され、この2つの既知事例の間に円滑なトレードオフをもたらす。
また、p$ と$q$ の両方が未知である寛容同値検定の問題についても同様の特徴を与える。
論文 参考訳(メタデータ) (2021-06-25T03:59:42Z) - 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) - Impact of Representation Learning in Linear Bandits [83.17684841392754]
本研究では,表現学習が帯域幅問題の効率性を向上させる方法について検討する。
我々は,$widetildeO(TsqrtkN + sqrtdkNT)$ regretを達成する新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-10-13T16:35:30Z) - Model-Free Reinforcement Learning: from Clipped Pseudo-Regret to Sample
Complexity [59.34067736545355]
S$状態、$A$アクション、割引係数$gamma in (0,1)$、近似しきい値$epsilon > 0$の MDP が与えられた場合、$epsilon$-Optimal Policy を学ぶためのモデルなしアルゴリズムを提供する。
十分小さな$epsilon$の場合、サンプルの複雑さで改良されたアルゴリズムを示す。
論文 参考訳(メタデータ) (2020-06-06T13:34:41Z) - Nearly Optimal Regret for Stochastic Linear Bandits with Heavy-Tailed
Payoffs [35.988644745703645]
我々は、リニアバンディットをヘビーテールのペイオフで分析し、そこではペイオフは1+epsilon$のモーメントしか持たない。
本稿では,$widetildeO(dfrac12Tfrac11+epsilon)$のサブ線形後悔境界を満足する2つの新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-04-28T13:01:38Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。