論文の概要: Asymptotically Optimal Information-Directed Sampling

• arxiv url: http://arxiv.org/abs/2011.05944v4
• Date: Fri, 2 Jul 2021 08:21:07 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-26 23:23:53.970710
• Title: Asymptotically Optimal Information-Directed Sampling
• Title（参考訳）: 漸近的最適情報指向サンプリング
• Authors: Johannes Kirschner, Tor Lattimore, Claire Vernade, Csaba Szepesv\'ari
• Abstract要約: 有限時間で最適であり、最悪の場合に最適である有限個の動作を持つ線形包帯に対する単純かつ効率的なアルゴリズムを導入する。 この手法は、高頻度情報指向サンプリング(IDS)フレームワークに基づいており、低境界を定義する最適化問題によって与えられる情報ゲインのサロゲートである。
• 参考スコア（独自算出の注目度）: 37.816004557470556
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We introduce a simple and efficient algorithm for stochastic linear bandits with finitely many actions that is asymptotically optimal and (nearly) worst-case optimal in finite time. The approach is based on the frequentist information-directed sampling (IDS) framework, with a surrogate for the information gain that is informed by the optimization problem that defines the asymptotic lower bound. Our analysis sheds light on how IDS balances the trade-off between regret and information and uncovers a surprising connection between the recently proposed primal-dual methods and the IDS algorithm. We demonstrate empirically that IDS is competitive with UCB in finite-time, and can be significantly better in the asymptotic regime.
• Abstract（参考訳）: 漸近的に最適であり、(ほぼ)最悪の場合を有限時間で最適とする確率線形包帯に対する単純かつ効率的なアルゴリズムを導入する。 このアプローチは、漸近的下界を定義する最適化問題によって通知される情報ゲインのためのサロゲートを備えた、頻繁な情報指向サンプリング(ids)フレームワークに基づいている。 我々の分析では、IDSが後悔と情報のトレードオフのバランスを保ち、最近提案された原始双対法とIDSアルゴリズムの驚くべき関係を明らかにする。 IDS が UCB と有限時間で競合し,無症候性体制において有意に良くなることを実証的に実証した。

関連論文リスト

• Diffusion Stochastic Optimization for Min-Max Problems [33.73046548872663]
  楽観的勾配法はミニマックス最適化問題に対処するのに有用である。 従来のバージョンでは大きなバッチサイズが必要であり,Samevareps-generativeOGOGと呼ばれる新しい定式化を導入,解析する。
  論文  参考訳（メタデータ） (2024-01-26T01:16:59Z)
• Weighted Averaged Stochastic Gradient Descent: Asymptotic Normality and Optimality [5.817158625734484]
  Gradient Descent (SGD) は、現代の統計学および機械学習において最も単純かつ最も人気のあるアルゴリズムの1つである。 異なる環境でのSGDの収束を加速するために、様々な平均化スキームが提案されている。
  論文  参考訳（メタデータ） (2023-07-13T17:29:01Z)
• Reweighted Interacting Langevin Diffusions: an Accelerated Sampling Methodfor Optimization [28.25662317591378]
  本稿では, サンプリング手法を高速化し, 難解な最適化問題の解法を提案する。 提案手法は, 後部分布サンプリングとLangevin Dynamicsを用いた最適化の関連性について検討する。
  論文  参考訳（メタデータ） (2023-01-30T03:48:20Z)
• Asymptotically Unbiased Instance-wise Regularized Partial AUC Optimization: Theory and Algorithm [101.44676036551537]
  One-way partial AUC (OPAUC) と Two-way partial AUC (TPAUC) はバイナリ分類器の平均性能を測定する。 既存の手法のほとんどはPAUCをほぼ最適化するしかなく、制御不能なバイアスにつながる。 本稿では,分散ロバスト最適化AUCによるPAUC問題の簡易化について述べる。
  論文  参考訳（メタデータ） (2022-10-08T08:26:22Z)
• Outlier-Robust Sparse Estimation via Non-Convex Optimization [73.18654719887205]
  空間的制約が存在する場合の高次元統計量と非破壊的最適化の関連について検討する。 これらの問題に対する新規で簡単な最適化法を開発した。 結論として、効率よくステーションに収束する一階法は、これらのタスクに対して効率的なアルゴリズムを導出する。
  論文  参考訳（メタデータ） (2021-09-23T17:38:24Z)
• An Asymptotically Optimal Primal-Dual Incremental Algorithm for Contextual Linear Bandits [129.1029690825929]
  複数の次元に沿った最先端技術を改善する新しいアルゴリズムを提案する。 非文脈線形帯域の特別な場合において、学習地平線に対して最小限の最適性を確立する。
  論文  参考訳（メタデータ） (2020-10-23T09:12:47Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Is Temporal Difference Learning Optimal? An Instance-Dependent Analysis [102.29671176698373]
  我々は、割引決定過程における政策評価の問題に対処し、生成モデルの下で、ll_infty$errorに対するマルコフに依存した保証を提供する。 我々は、ポリシー評価のために、局所ミニマックス下限の両漸近バージョンと非漸近バージョンを確立し、アルゴリズムを比較するためのインスタンス依存ベースラインを提供する。
  論文  参考訳（メタデータ） (2020-03-16T17:15:28Z)

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

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