論文の概要: High-Dimensional Sparse Linear Bandits
- arxiv url: http://arxiv.org/abs/2011.04020v2
- Date: Sat, 4 Sep 2021 13:13:12 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-28 08:19:46.446555
- Title: High-Dimensional Sparse Linear Bandits
- Title(参考訳): 高次元スパース線形バンディット
- Authors: Botao Hao, Tor Lattimore, Mengdi Wang
- Abstract要約: データ・ポーア・システマティクスにおける疎線形包帯に対して、新しい$Omega(n2/3)$ dimension-free minimax regret lower boundを導出する。
また、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$O(sqrtn)$ regret上界も証明する。
- 参考スコア(独自算出の注目度): 67.9378546011416
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Stochastic linear bandits with high-dimensional sparse features are a
practical model for a variety of domains, including personalized medicine and
online advertising. We derive a novel $\Omega(n^{2/3})$ dimension-free minimax
regret lower bound for sparse linear bandits in the data-poor regime where the
horizon is smaller than the ambient dimension and where the feature vectors
admit a well-conditioned exploration distribution. This is complemented by a
nearly matching upper bound for an explore-then-commit algorithm showing that
that $\Theta(n^{2/3})$ is the optimal rate in the data-poor regime. The results
complement existing bounds for the data-rich regime and provide another example
where carefully balancing the trade-off between information and regret is
necessary. Finally, we prove a dimension-free $O(\sqrt{n})$ regret upper bound
under an additional assumption on the magnitude of the signal for relevant
features.
- Abstract(参考訳): 高次元のスパース特徴を持つ確率的線形バンディットは、パーソナライズされた医療やオンライン広告を含む様々なドメインの実用的なモデルである。
我々は、地平線が周囲の次元よりも小さく、特徴ベクトルがよく条件付き探索分布を許容するデータ・ポーア・システレーションにおいて、疎線型包帯に対する次元自由なミニマックスの最小境界を導出する。
これは、$\Theta(n^{2/3})$がデータ・ポーア・システマティクスの最適レートであることを示す探索列-コミット・アルゴリズムのほぼ一致する上限によって補完される。
結果は、データリッチな体制に対する既存の境界を補完し、情報と後悔の間のトレードオフを慎重にバランスする別の例を提供する。
最後に、関連する特徴に対する信号の大きさに関する追加の仮定の下で、次元のない$o(\sqrt{n})$ regret upperboundを証明する。
関連論文リスト
- FLIPHAT: Joint Differential Privacy for High Dimensional Sparse Linear Bandits [8.908421753758475]
高次元スパース線形帯域は、シーケンシャルな意思決定問題の効率的なモデルとして機能する。
データプライバシの懸念により、我々は、共同でプライベートな高次元の疎線形帯域について検討する。
FLIPHATは,プライバシパラメータの点で最適に後悔することを示す。
論文 参考訳(メタデータ) (2024-05-22T22:19:12Z) - Symmetric Linear Bandits with Hidden Symmetry [17.40632789343385]
学習者から対称性を隠蔽する高次元対称線形包帯について検討する。
低次元部分空間の集合におけるモデル選択に基づく手法を提案する。
論文 参考訳(メタデータ) (2024-05-22T18:11:57Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - Cooperative Thresholded Lasso for Sparse Linear Bandit [6.52540785559241]
本稿では,マルチエージェント・スパース文脈線形帯域問題に対処する新しい手法を提案する。
疎線形帯域における行単位の分散データに対処する最初のアルゴリズムである。
後悔を最小限に抑えるために効率的な特徴抽出が重要となる高次元マルチエージェント問題に適用可能である。
論文 参考訳(メタデータ) (2023-05-30T16:05:44Z) - Borda Regret Minimization for Generalized Linear Dueling Bandits [65.09919504862496]
本稿では,ボルダスコアが最も高い項目を識別することを目的とした,デュエルバンディットに対するボルダ後悔最小化問題について検討する。
本稿では,多くの既存モデルをカバーする一般化線形デュエルバンドモデルのリッチクラスを提案する。
我々のアルゴリズムは$tildeO(d2/3 T2/3)$ regretを達成し、これも最適である。
論文 参考訳(メタデータ) (2023-03-15T17:59:27Z) - Exploration in Linear Bandits with Rich Action Sets and its Implications
for Inference [23.364534479492715]
期待行列の最小固有値は、アルゴリズムの累積後悔が$sqrtn)$であるときに、$Omega(sqrtn)として増加することを示す。
本研究は, 線形帯域におけるEmphmodel selectionとEmphclusteringの2つの実践シナリオに適用する。
論文 参考訳(メタデータ) (2022-07-23T20:25:07Z) - Minimax Optimal Quantization of Linear Models: Information-Theoretic
Limits and Efficient Algorithms [59.724977092582535]
測定から学習した線形モデルの定量化の問題を考える。
この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。
本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
論文 参考訳(メタデータ) (2022-02-23T02:39:04Z) - Universal and data-adaptive algorithms for model selection in linear
contextual bandits [52.47796554359261]
モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。
データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。
我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
論文 参考訳(メタデータ) (2021-11-08T18:05:35Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。