論文の概要: Variance-Aware Sparse Linear Bandits
- arxiv url: http://arxiv.org/abs/2205.13450v1
- Date: Thu, 26 May 2022 15:55:44 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-27 12:39:37.359360
- Title: Variance-Aware Sparse Linear Bandits
- Title（参考訳）: 可変型スパースリニアバンド
- Authors: Yan Dai, Ruosong Wang and Simon S. Du
- Abstract要約: 余分な線形包帯に対する最悪のミニマックスは$widetildeThetaleft(sqrtdTright)$である。
ノイズがなく、アクションセットが単位球面である良性設定では、ディビジョン・アンド・コンカーを使用して、$widetildemathcal O(1)$ regretを達成することができる。
我々は,任意の分散対応線形帯域幅アルゴリズムを分散対応線形帯域幅アルゴリズムに変換する汎用フレームワークを開発した。
- 参考スコア（独自算出の注目度）: 64.70681598741417
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: It is well-known that the worst-case minimax regret for sparse linear bandits
is $\widetilde{\Theta}\left(\sqrt{dT}\right)$ where $d$ is the ambient
dimension and $T$ is the number of time steps (ignoring the dependency on
sparsity). On the other hand, in the benign setting where there is no noise and
the action set is the unit sphere, one can use divide-and-conquer to achieve an
$\widetilde{\mathcal O}(1)$ regret, which is (nearly) independent of $d$ and
$T$. In this paper, we present the first variance-aware regret guarantee for
sparse linear bandits: $\widetilde{\mathcal O}\left(\sqrt{d\sum_{t=1}^T
\sigma_t^2} + 1\right)$, where $\sigma_t^2$ is the variance of the noise at the
$t$-th time step. This bound naturally interpolates the regret bounds for the
worst-case constant-variance regime ($\sigma_t = \Omega(1)$) and the benign
deterministic regimes ($\sigma_t = 0$). To achieve this variance-aware regret
guarantee, we develop a general framework that converts any variance-aware
linear bandit algorithm to a variance-aware algorithm for sparse linear bandits
in a ``black-box'' manner. Specifically, we take two recent algorithms as black
boxes to illustrate that the claimed bounds indeed hold, where the first
algorithm can handle unknown-variance cases and the second one is more
efficient.
- Abstract（参考訳）: スパース線形バンドに対する最悪のミニマックスの後悔は、$\widetilde{\theta}\left(\sqrt{dt}\right)$である。
一方、ノイズがなく、アクションセットが単位球面である良心的な設定では、$$d$と$T$とは(ほぼ)独立な$\widetilde{\mathcal O}(1)の後悔を達成するために、ディビジョン・アンド・コンカーを使うことができる。
本稿では、疎線形包帯に対する最初の分散対応後悔保証を示す: $\widetilde{\mathcal O}\left(\sqrt{d\sum_{t=1}^T \sigma_t^2} + 1\right)$, where $\sigma_t^2$ is the variance of the noise at the $t-th time step。
この境界は、最悪ケースの定数分散レジーム(\sigma_t = \Omega(1)$)と良性決定論的レジーム(\sigma_t = 0$)の後悔境界を自然に補間する。
そこで本研究では,分散認識線形バンディットアルゴリズムを,分散認識線形バンディットを‘ブラックボックス’方式で分散認識アルゴリズムに変換する汎用フレームワークを開発した。
具体的には、2つの最近のアルゴリズムをブラックボックスとして、要求される境界が実際に保持されていることを示す。
関連論文リスト
- Restless Linear Bandits [5.00389879175348]
未知の$mathbbRd$-valued stationary $varphi$-mixing sequence of parameters $(theta_t,t in mathbbN)$ が存在すると仮定される。
指数混合率が$theta_t$の場合、LinMix-UCBと呼ばれる楽観的なアルゴリズムが提案される。
論文 参考訳（メタデータ） (2024-05-17T14:37:39Z) - Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。
Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。
特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
論文 参考訳（メタデータ） (2024-03-15T23:36:55Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。
政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。
提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
論文 参考訳（メタデータ） (2024-02-24T06:36:08Z) - First- and Second-Order Bounds for Adversarial Linear Contextual Bandits [22.367921675238318]
我々は,K$の腕に付随する損失関数を制限なく時間とともに変化させることができる,逆線形文脈帯域設定を考える。
V_T$ または $L_T*$ は$T$ よりもかなり小さい可能性があるため、環境が比較的良心的であれば、最悪の場合の後悔よりも改善される。
論文 参考訳（メタデータ） (2023-05-01T14:00:15Z) - Computationally Efficient Horizon-Free Reinforcement Learning for Linear
Mixture MDPs [111.75736569611159]
線形混合MDPのための計算効率のよい初めての地平線フリーアルゴリズムを提案する。
我々のアルゴリズムは、未知の遷移力学に対する重み付き最小二乗推定器に適応する。
これにより、$sigma_k2$'sが知られているときに、この設定で最もよく知られたアルゴリズムも改善される。
論文 参考訳（メタデータ） (2022-05-23T17:59:18Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - On Submodular Contextual Bandits [92.45432756301231]
作用が基底集合の部分集合であり、平均報酬が未知の単調部分モジュラ函数によってモデル化されるような文脈的包帯の問題を考える。
Inverse Gap Weighting 戦略により,提案アルゴリズムは推定関数の局所的最適度を効率よくランダム化することを示す。
論文 参考訳（メタデータ） (2021-12-03T21:42:33Z) - Variance-Aware Confidence Set: Variance-Dependent Bound for Linear
Bandits and Horizon-Free Bound for Linear Mixture MDP [76.94328400919836]
線形バンドイットと線形混合決定プロセス(mdp)に対する分散認識信頼セットの構築方法を示す。
線形バンドイットに対しては、$d を特徴次元とする$widetildeo(mathrmpoly(d)sqrt1 + sum_i=1ksigma_i2) が成り立つ。
線形混合 MDP に対し、$widetildeO(mathrmpoly(d)sqrtK)$ regret bound を得る。
論文 参考訳（メタデータ） (2021-01-29T18:57:52Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。