論文の概要: Model Selection for Generic Contextual Bandits

• arxiv url: http://arxiv.org/abs/2107.03455v2
• Date: Thu, 20 Jul 2023 11:54:22 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-21 19:26:49.047491
• Title: Model Selection for Generic Contextual Bandits
• Title（参考訳）: ジェネリックコンテキスト帯域のモデル選択
• Authors: Avishek Ghosh, Abishek Sankararaman and Kannan Ramchandran
• Abstract要約: 適応文脈帯域(tt Family ACB)と呼ばれる改良型アルゴリズムを提案する。 我々は、このアルゴリズムが適応的であること、すなわち、リットレートが任意の証明可能な文脈帯域幅アルゴリズムと整合していることを証明する。 また,真のモデルクラスを知らないにもかかわらず,ETCスタイルのアルゴリズムでも同様の後悔境界が得られることを示す。
• 参考スコア（独自算出の注目度）: 20.207989166682832
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of model selection for the general stochastic contextual bandits under the realizability assumption. We propose a successive refinement based algorithm called Adaptive Contextual Bandit ({\ttfamily ACB}), that works in phases and successively eliminates model classes that are too simple to fit the given instance. We prove that this algorithm is adaptive, i.e., the regret rate order-wise matches that of any provable contextual bandit algorithm (ex. \cite{falcon}), that needs the knowledge of the true model class. The price of not knowing the correct model class turns out to be only an additive term contributing to the second order term in the regret bound. This cost possess the intuitive property that it becomes smaller as the model class becomes easier to identify, and vice-versa. We also show that a much simpler explore-then-commit (ETC) style algorithm also obtains similar regret bound, despite not knowing the true model class. However, the cost of model selection is higher in ETC as opposed to in {\ttfamily ACB}, as expected. Furthermore, for the special case of linear contextual bandits, we propose specialized algorithms that obtain sharper guarantees compared to the generic setup.
• Abstract（参考訳）: 一般化可能性仮定の下では,一般確率的文脈帯域のモデル選択の問題を考える。 そこで本研究では,適応的文脈的バンドイット({\ttfamily acb})と呼ばれる逐次改良型アルゴリズムを提案する。 このアルゴリズムが適応的であること、すなわち、後悔率の順序付けは、証明可能な文脈的バンディットアルゴリズムのそれと一致することを証明する。 これは真のモデルクラスの知識を必要とする。 正しいモデルクラスを知らないという価格は、後悔境界における第二次項に寄与する加法項のみであることが判明した。 このコストはモデルクラスが識別しやすくなり、逆もまたより小さくなるという直感的な特性を持っている。 また,真のモデルクラスを知らないにもかかわらず,ETCスタイルのアルゴリズムでも同様の後悔境界が得られることを示す。 しかし、モデル選択のコストは予想通り in {\ttfamily acb} よりも高い。 さらに,線形文脈バンディットの特別な場合に対して,汎用的な構成に比べてシャープな保証を得るための特別なアルゴリズムを提案する。

関連論文リスト

• Bad Values but Good Behavior: Learning Highly Misspecified Bandits and MDPs [16.777565006843012]
  パラメトリックな特徴に基づく報酬モデルが,帯域幅やマルコフ決定プロセス(MDP)などの意思決定設定において,さまざまなアルゴリズムによって採用されている。 我々は、$epsilon$-greedyやLinUCB、それに適合したQラーニングといった基本的なアルゴリズムが、非常に不明瞭なモデルの下で、最適ポリシーを確実に学習していることを示します。 これは、例えば、時間とともに線形にスケールする後悔の束縛を示す不特定な包帯に対する既存の最悪の結果とは対照的であり、不特定に頑丈な非自明に大規模な包帯例が存在することを示している。
  論文  参考訳（メタデータ） (2023-10-13T18:53:30Z)
• 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)
• Fast Feature Selection with Fairness Constraints [49.142308856826396]
  モデル構築における最適特徴の選択に関する基礎的問題について検討する。 この問題は、greedyアルゴリズムの変種を使用しても、大規模なデータセットで計算的に困難である。 適応クエリモデルは,最近提案された非モジュラー関数に対する直交整合探索のより高速なパラダイムに拡張する。 提案アルゴリズムは、適応型クエリモデルにおいて指数関数的に高速な並列実行を実現する。
  論文  参考訳（メタデータ） (2022-02-28T12:26:47Z)
• Universal and data-adaptive algorithms for model selection in linear contextual bandits [52.47796554359261]
  モデル選択の最も単純な非自明な例を考える: 単純な多重武装バンディット問題と線形文脈バンディット問題とを区別する。 データ適応的な方法で探索する新しいアルゴリズムを導入し、$mathcalO(dalpha T1- alpha)$という形式の保証を提供する。 我々のアプローチは、いくつかの仮定の下で、ネストされた線形文脈包帯のモデル選択に拡張する。
  論文  参考訳（メタデータ） (2021-11-08T18:05:35Z)
• Near Instance Optimal Model Selection for Pure Exploration Linear Bandits [20.67688737534517]
  純探索線形帯域設定におけるモデル選択問題について検討する。 私たちのゴールは、最小の仮説クラスのインスタンス依存の複雑性尺度に自動的に適応することです。 提案アルゴリズムは,実験設計に基づく新しい最適化問題を定義する。
  論文  参考訳（メタデータ） (2021-09-10T22:56:58Z)
• 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)
• Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
  基本アルゴリズムを選択できるメタアルゴリズムを開発した。 基本アルゴリズムの1つが$O(sqrtT)$後悔している場合でも、一般的には$Omega(sqrtT)$後悔よりも良いものを得ることはできません。
  論文  参考訳（メタデータ） (2020-03-03T18:46:34Z)
• Progressive Identification of True Labels for Partial-Label Learning [112.94467491335611]
  部分ラベル学習(Partial-label Learning, PLL)は、典型的な弱教師付き学習問題であり、各トレーニングインスタンスには、真のラベルである候補ラベルのセットが設けられている。 既存のほとんどの手法は、特定の方法で解決しなければならない制約付き最適化として精巧に設計されており、計算複雑性をビッグデータにスケールアップするボトルネックにしている。 本稿では,モデルと最適化アルゴリズムの柔軟性を備えた分類器の新しいフレームワークを提案する。
  論文  参考訳（メタデータ） (2020-02-19T08:35:15Z)

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

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