論文の概要: Universal and data-adaptive algorithms for model selection in linear contextual bandits

• arxiv url: http://arxiv.org/abs/2111.04688v1
• Date: Mon, 8 Nov 2021 18:05:35 GMT
• ステータス: 処理完了
• システム内更新日: 2021-11-09 15:00:02.642952
• Title: Universal and data-adaptive algorithms for model selection in linear contextual bandits
• Title（参考訳）: 線形文脈帯域におけるモデル選択のためのユニバーサルおよびデータ適応アルゴリズム
• Authors: Vidya Muthukumar, Akshay Krishnamurthy
• Abstract要約: モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
• 参考スコア（独自算出の注目度）: 52.47796554359261
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Model selection in contextual bandits is an important complementary problem to regret minimization with respect to a fixed model class. We consider the simplest non-trivial instance of model-selection: distinguishing a simple multi-armed bandit problem from a linear contextual bandit problem. Even in this instance, current state-of-the-art methods explore in a suboptimal manner and require strong "feature-diversity" conditions. In this paper, we introduce new algorithms that a) explore in a data-adaptive manner, and b) provide model selection guarantees of the form $\mathcal{O}(d^{\alpha} T^{1- \alpha})$ with no feature diversity conditions whatsoever, where $d$ denotes the dimension of the linear model and $T$ denotes the total number of rounds. The first algorithm enjoys a "best-of-both-worlds" property, recovering two prior results that hold under distinct distributional assumptions, simultaneously. The second removes distributional assumptions altogether, expanding the scope for tractable model selection. Our approach extends to model selection among nested linear contextual bandits under some additional assumptions.
• Abstract（参考訳）: 文脈的包帯におけるモデル選択は、固定モデルクラスに対する最小化を後悔する重要な相補的問題である。 モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 この例でさえ、現在の最先端の手法は最適でない方法で探索し、強い「特徴の多様性」条件を必要とする。 本稿では,新しいアルゴリズムを提案する。 a) データ適応的な方法で探索し、 b) $\mathcal{O}(d^{\alpha} T^{1- \alpha})$ という形のモデル選択を保証する。 第1のアルゴリズムは「世界のベスト」な性質を享受し、異なる分布仮定の下で同時に保持される2つの前の結果を回復する。 後者は分布的仮定を完全に取り除き、扱いやすいモデル選択のスコープを広げる。 提案手法は,ネストした線形コンテキストバンディット間のモデル選択に拡張する。

関連論文リスト

• Anytime Model Selection in Linear Bandits [61.97047189786905]
  ALEXPは,その後悔に対するM$への依存を指数関数的に改善した。 提案手法は,オンライン学習と高次元統計学の新たな関連性を確立するために,ラッソの時間的一様解析を利用する。
  論文  参考訳（メタデータ） (2023-07-24T15:44:30Z)
• Oracle Inequalities for Model Selection in Offline Reinforcement Learning [105.74139523696284]
  本稿では,値関数近似を用いたオフラインRLにおけるモデル選択の問題について検討する。 対数係数まで最小値の速度-最適不等式を実現するオフラインRLの最初のモデル選択アルゴリズムを提案する。 そこで本研究では,優れたモデルクラスを確実に選択できることを示す数値シミュレーションを行った。
  論文  参考訳（メタデータ） (2022-11-03T17:32:34Z)
• Combinatorial Causal Bandits [25.012065471684025]
  因果的包帯において、学習エージェントは、各ラウンドで最大$K$変数を選択して介入し、ターゲット変数$Y$に対する期待される後悔を最小限にすることを目的としている。 因果モデルの簡潔なパラメトリック表現を用いた二元一般化線形モデル(BGLM)の文脈下で検討する。 マルコフ BGLM に対するアルゴリズム BGLM-OFU を最大推定法に基づいて提案し,O(sqrtTlog T)$ regret, ここでは$T$ が時間地平線となることを示す。
  論文  参考訳（メタデータ） (2022-06-04T14:14:58Z)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits [20.67688737534517]
  純探索線形帯域設定におけるモデル選択問題について検討する。 私たちのゴールは、最小の仮説クラスのインスタンス依存の複雑性尺度に自動的に適応することです。 提案アルゴリズムは,実験設計に基づく新しい最適化問題を定義する。
  論文  参考訳（メタデータ） (2021-09-10T22:56:58Z)
• Model Selection for Generic Contextual Bandits [20.207989166682832]
  適応文脈帯域(tt Family ACB)と呼ばれる改良型アルゴリズムを提案する。 我々は、このアルゴリズムが適応的であること、すなわち、リットレートが任意の証明可能な文脈帯域幅アルゴリズムと整合していることを証明する。 また,真のモデルクラスを知らないにもかかわらず,ETCスタイルのアルゴリズムでも同様の後悔境界が得られることを示す。
  論文  参考訳（メタデータ） (2021-07-07T19:35:31Z)
• Towards Costless Model Selection in Contextual Bandits: A Bias-Variance Perspective [7.318831153179727]
  文脈的包帯設定における累積的後悔最小化のための同様の保証の実現可能性について検討した。 提案アルゴリズムは, 新たな不特定性テストに基づいており, モデル選択による報酬推定の利点を実証する。
  論文  参考訳（メタデータ） (2021-06-11T16:08:03Z)
• Pareto Optimal Model Selection in Linear Bandits [15.85873315624132]
  本研究では,学習者が最適仮説クラスの次元に適応しなければならない線形帯域設定におけるモデル選択問題について検討する。 本稿では,まず,固定アクション集合であっても,未知の内在次元$d_star$ への適応がコスト的に現れることを示す下限を定式化する。
  論文  参考訳（メタデータ） (2021-02-12T16:02:06Z)
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature [61.22680308681648]
  決定論的報酬を有する1層ニューラルネットバンディットにおいても,グローバル収束は統計的に難解であることを示す。 非線形バンディットとRLの両方に対して,オンラインモデル学習者による仮想アセンジ(Virtual Ascent with Online Model Learner)というモデルベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-08T12:41:56Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  乗算重み更新法に基づいて,Klivans と Meka のアルゴリズムを適用した。 アルゴリズムは、文献の他のものと質的に類似したサンプル複雑性境界を楽しみます。 ランタイムが低い$O(mp2)$で、$m$サンプルと$p$ノードの場合には、簡単にオンライン形式で実装できる。
  論文  参考訳（メタデータ） (2020-02-20T10:50:58Z)

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

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