論文の概要: 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)$クエリが可能であることをさらに示します。
これらの結果は,不特定バンディット学習において空間性がいかに有効であるかを概観し,不特定バンディット学習や強化学習において線形特徴がいつ有用であるかをより深く理解する。
関連論文リスト
- Sample-Efficient Linear Regression with Self-Selection Bias [7.605563562103568]
未知のインデックス設定における自己選択バイアスを伴う線形回帰の問題を考察する。
我々は,$mathbfw_1,ldots,mathbfw_kinを復元する,新しい,ほぼ最適なサンプル効率($k$)アルゴリズムを提案する。
このアルゴリズムは雑音の仮定をかなり緩めることに成功し、従って関連する最大線形回帰の設定にも成功している。
論文 参考訳(メタデータ) (2024-02-22T02:20:24Z) - Towards Characterizing the First-order Query Complexity of Learning
(Approximate) Nash Equilibria in Zero-sum Matrix Games [0.0]
正確な平衡は$O(fracln Kepsilon)$クエリの代わりに$O(fracln Kepsilon)$から効率的に計算できることを示す。
我々は下界に対する新しい手法を導入し、任意の$epsilon leq 1 / (cK4)$に対して$tildeOmega(frac1Kepsilon)$の下位境界を得ることができる。
論文 参考訳(メタデータ) (2023-04-25T12:42:59Z) - Optimal Sketching Bounds for Sparse Linear Regression [116.30196615349226]
我々は、$ell_p$ノルムや広範なヒンジ様損失関数のクラスから、様々な損失関数の下で、$k$スパース線形回帰の難読スケッチを研究する。
スパース$ell$varepsレグレッションの場合、$Theta(klog(d/k)/varepsilon2)$ rowsでスケッチの上に曖昧な分布が存在し、これは定数要素に固執することを示している。
また、$O(mu2 klog(mun d/varepsilon)/varのスケッチも示します。
論文 参考訳(メタデータ) (2023-04-05T07:24:19Z) - 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) - Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
我々は、$AinmathbbRdtimes n$へのアクセスを考えると、潜入$k$-vertex simplex $KsubsetmathbbRdtimes n$を学習する問題を考える。
実行時間における$k$への依存は、トップ$k$特異値の質量が$a$であるという自然な仮定から不要であることを示す。
論文 参考訳(メタデータ) (2021-05-17T16:40:48Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。