論文の概要: Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design

• arxiv url: http://arxiv.org/abs/2007.01980v3
• Date: Fri, 23 Apr 2021 13:01:03 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-13 13:20:42.952044
• Title: Linear Bandits with Limited Adaptivity and Learning Distributional Optimal Design
• Title（参考訳）: 適応性に制限のある線形帯域と分布最適設計の学習
• Authors: Yufei Ruan, Jiaqi Yang, Yuan Zhou
• Abstract要約: オンライン能動学習の中心的課題である線形文脈帯域に対する適応性制約の影響について検討する。 文脈ベクトルが$d$次元線形文脈包帯で逆選択された場合、学習者はミニマックス最適後悔を達成するために$O(d log d log T)$ポリシースイッチが必要であることを示す。
• 参考スコア（独自算出の注目度）: 12.465883735626605
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Motivated by practical needs such as large-scale learning, we study the impact of adaptivity constraints to linear contextual bandits, a central problem in online active learning. We consider two popular limited adaptivity models in literature: batch learning and rare policy switches. We show that, when the context vectors are adversarially chosen in $d$-dimensional linear contextual bandits, the learner needs $O(d \log d \log T)$ policy switches to achieve the minimax-optimal regret, and this is optimal up to $\mathrm{poly}(\log d, \log \log T)$ factors; for stochastic context vectors, even in the more restricted batch learning model, only $O(\log \log T)$ batches are needed to achieve the optimal regret. Together with the known results in literature, our results present a complete picture about the adaptivity constraints in linear contextual bandits. Along the way, we propose the distributional optimal design, a natural extension of the optimal experiment design, and provide a both statistically and computationally efficient learning algorithm for the problem, which may be of independent interest.
• Abstract（参考訳）: 大規模学習などの実践的なニーズに動機付けられ,オンライン活動学習の中心的課題である線形文脈帯域に対する適応性制約の影響について検討した。 文学において、バッチ学習とまれなポリシースイッチという2つの一般的な限定適応モデルを考える。 文脈ベクトルが$d$次元線形文脈包帯に逆向きに選択された場合、学習者はミニマックス最適後悔を達成するために$O(d \log d \log T)$ポリシースイッチを必要とし、これは最適である$\mathrm{poly}(\log d, \log \log T)$ factor; より制限されたバッチ学習モデルであっても確率的文脈ベクトルは$O(\log \log T)$バッチのみが最適後悔を達成するために必要であることを示す。 文献上の既知の結果と合わせて,線形文脈バンディットにおける適応性制約に関する全体像を示す。 そこで本研究では,最適実験設計の自然な拡張である分布最適設計を提案し,その問題に対する統計的かつ計算効率のよい学習アルゴリズムを提供する。

関連論文リスト

• Anytime Model Selection in Linear Bandits [61.97047189786905]
  ALEXPは,その後悔に対するM$への依存を指数関数的に改善した。 提案手法は,オンライン学習と高次元統計学の新たな関連性を確立するために,ラッソの時間的一様解析を利用する。
  論文  参考訳（メタデータ） (2023-07-24T15:44:30Z)
• Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach [57.92727189589498]
  本稿では,2段階の適応性を持つオンライン凸最適化手法を提案する。 我々は$mathcalO(log V_T)$, $mathcalO(d log V_T)$, $hatmathcalO(sqrtV_T)$ regret bounds for strong convex, exp-concave and convex loss function。
  論文  参考訳（メタデータ） (2023-07-17T09:55:35Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。 対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。 そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
  論文  参考訳（メタデータ） (2022-11-03T17:32:34Z)
• Efficient and Near-Optimal Smoothed Online Learning for Generalized Linear Functions [28.30744223973527]
  我々は,K-wise線形分類において,統計学的に最適なログ(T/sigma)の後悔を初めて楽しむ計算効率のよいアルゴリズムを提案する。 一般化線形分類器によって誘導される不一致領域の幾何学の新たな特徴付けを開発する。
  論文  参考訳（メタデータ） (2022-05-25T21:31:36Z)
• Stochastic Contextual Dueling Bandits under Linear Stochastic Transitivity Models [25.336599480692122]
  我々は,コンテキスト情報を用いた決闘バンディット問題における後悔の最小化タスクについて検討する。 本稿では,フィードバックプロセスの模倣に基づく計算効率のよいアルゴリズムである$texttCoLSTIM$を提案する。 本実験は,CoLSTモデルの特殊事例に対する最先端アルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2022-02-09T17:44:19Z)
• Adapting to Misspecification in Contextual Bandits [82.55565343668246]
  我々は、$varepsilon$-misspecified contextual banditsに対して、新しいオラクル効率アルゴリズム群を導入する。 我々は、未知の不特定値に対して最適な$O(dsqrtT + varepsilonsqrtdT)$ regret boundを達成する最初のアルゴリズムを得る。
  論文  参考訳（メタデータ） (2021-07-12T21:30:41Z)
• Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
  本研究では,学習者が最適仮説クラスの次元に適応しなければならない線形帯域設定におけるモデル選択問題について検討する。 本稿では,まず,固定アクション集合であっても,未知の内在次元$d_star$ への適応がコスト的に現れることを示す下限を定式化する。
  論文  参考訳（メタデータ） (2021-02-12T16:02:06Z)
• Online Model Selection for Reinforcement Learning with Function Approximation [50.008542459050155]
  我々は、$tildeO(L5/6 T2/3)$ regretで最適な複雑性に適応するメタアルゴリズムを提案する。 また、メタアルゴリズムは、インスタンス依存の後悔境界を著しく改善することを示す。
  論文  参考訳（メタデータ） (2020-11-19T10:00:54Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。 この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。 本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
  論文  参考訳（メタデータ） (2020-09-04T04:10:39Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。