論文の概要: Estimating Optimal Policy Value in General Linear Contextual Bandits

• arxiv url: http://arxiv.org/abs/2302.09451v1
• Date: Sun, 19 Feb 2023 01:09:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-21 18:27:13.915711
• Title: Estimating Optimal Policy Value in General Linear Contextual Bandits
• Title（参考訳）: 一般線形帯域における最適政策値の推定
• Authors: Jonathan N. Lee, Weihao Kong, Aldo Pacchiano, Vidya Muthukumar, Emma Brunskill
• Abstract要約: 多くのバンドイット問題において、政策によって達成可能な最大報酬は、前もって不明であることが多い。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 V*$で問題依存上界を推定する,より実用的で効率的なアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 50.008542459050155
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In many bandit problems, the maximal reward achievable by a policy is often unknown in advance. We consider the problem of estimating the optimal policy value in the sublinear data regime before the optimal policy is even learnable. We refer to this as $V^*$ estimation. It was recently shown that fast $V^*$ estimation is possible but only in disjoint linear bandits with Gaussian covariates. Whether this is possible for more realistic context distributions has remained an open and important question for tasks such as model selection. In this paper, we first provide lower bounds showing that this general problem is hard. However, under stronger assumptions, we give an algorithm and analysis proving that $\widetilde{\mathcal{O}}(\sqrt{d})$ sublinear estimation of $V^*$ is indeed information-theoretically possible, where $d$ is the dimension. We then present a more practical, computationally efficient algorithm that estimates a problem-dependent upper bound on $V^*$ that holds for general distributions and is tight when the context distribution is Gaussian. We prove our algorithm requires only $\widetilde{\mathcal{O}}(\sqrt{d})$ samples to estimate the upper bound. We use this upper bound and the estimator to obtain novel and improved guarantees for several applications in bandit model selection and testing for treatment effects.
• Abstract（参考訳）: 多くのバンディット問題において、政策によって達成可能な最大報酬はしばしば前もって不明である。 我々は,最適政策が学習される前に,サブ線形データ構造における最適政策値を推定する問題を考察する。 これを$V^*$推定と呼ぶ。 最近、高速$v^*$推定が可能であるが、ガウス共変量を持つ不連続な線形バンディットでのみ可能であることが示されている。 より現実的なコンテキスト分布に対してこれが可能かどうかは、モデル選択のようなタスクに対してオープンで重要な質問である。 本稿では、まず、この一般的な問題が難しいことを示す下限を示す。 しかし、より強い仮定の下では、$\widetilde{\mathcal{O}}(\sqrt{d})$ $V^*$ のサブ線形推定が実際には情報理論的に可能であり、$d$ が次元であることを示すアルゴリズムと解析を与える。 次に, 一般分布に留まり, 文脈分布がガウス分布である場合の密接である$v^*$上の問題依存上限を推定する, より実用的で計算効率の高いアルゴリズムを提案する。 我々のアルゴリズムは上限を推定するために$\widetilde{\mathcal{O}}(\sqrt{d})$サンプルのみを必要とすることを証明している。 我々は,この上限値と推定器を用いて,バンディットモデル選択および治療効果試験におけるいくつかの応用の新規かつ改善された保証を得る。

関連論文リスト

• Model Predictive Control is Almost Optimal for Restless Bandit [2.295863158976069]
  離散時間無限水平平均報酬(RMAB)問題を考える。 本稿では, 回転型計算水平方向を$tau$とする非定常ポリシーを提案する。 局所安定性条件下では、その部分最適性ギャップは一般に$O(1/sqrtN)$、$exp(-Omega(N))$である。
  論文  参考訳（メタデータ） (2024-10-08T19:34:23Z)
• Variance-Dependent Regret Bounds for Non-stationary Linear Bandits [52.872628573907434]
  報酬分布の分散と$B_K$の分散を利用するアルゴリズムを提案する。 Restarted Weighted$textOFUL+$とRestarted$textSAVE+$の2つの新しいアルゴリズムを紹介します。 特に、V_K$が$K$よりはるかに小さい場合、我々のアルゴリズムは、異なる設定下での非定常線形バンドレットの最先端結果よりも優れている。
  論文  参考訳（メタデータ） (2024-03-15T23:36:55Z)
• Robust Sparse Estimation for Gaussians with Optimal Error under Huber Contamination [42.526664955704746]
  本研究では,平均推定,PCA,線形回帰に着目したハマー汚染モデルにおけるスパース推定タスクについて検討する。 それぞれのタスクに対して、最適なエラー保証を備えた最初のサンプルと計算効率の良い頑健な推定器を与える。 技術レベルでは、スパース方式における新しい多次元フィルタリング法を開発し、他の応用を見出すことができる。
  論文  参考訳（メタデータ） (2024-03-15T15:51:27Z)
• Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
  本稿では,政策評価,最良政策識別,後悔の最小化のための効率的なアルゴリズムを提案する。 政策評価と最良の政策識別のために,我々のアルゴリズムは最小限に最適であることを示す。 提案アルゴリズムは、まずスペクトル法を利用して、低ランク報酬行列の左特異部分空間と右特異部分空間を推定する。
  論文  参考訳（メタデータ） (2024-02-24T06:36:08Z)
• Efficient Frameworks for Generalized Low-Rank Matrix Bandit Problems [61.85150061213987]
  一般化線形モデル (GLM) フレームワークを用いて, citelu2021low で提案した一般化低ランク行列帯域問題について検討する。 既存のアルゴリズムの計算不可能性と理論的制約を克服するため,まずG-ESTTフレームワークを提案する。 G-ESTT は $tildeO(sqrt(d_1+d_2)3/2Mr3/2T)$ bound of regret を達成でき、G-ESTS は $tildeO を達成できることを示す。
  論文  参考訳（メタデータ） (2024-01-14T14:14:19Z)
• Optimality in Mean Estimation: Beyond Worst-Case, Beyond Sub-Gaussian, and Beyond $1+\alpha$ Moments [10.889739958035536]
  本稿では,アルゴリズムの微細な最適性を分析するための新しい定義フレームワークを提案する。 平均値の中央値は近傍最適であり, 一定の要因が得られている。 定数係数のずれのない近傍分離推定器を見つけることは自由である。
  論文  参考訳（メタデータ） (2023-11-21T18:50:38Z)
• Best Policy Identification in Linear MDPs [70.57916977441262]
  縮退した線形マルコフ+デルタ決定における最適同定問題について, 生成モデルに基づく固定信頼度設定における検討を行った。 複雑な非最適化プログラムの解としての下位境界は、そのようなアルゴリズムを考案する出発点として用いられる。
  論文  参考訳（メタデータ） (2022-08-11T04:12:50Z)
• Minimax Optimal Quantization of Linear Models: Information-Theoretic Limits and Efficient Algorithms [59.724977092582535]
  測定から学習した線形モデルの定量化の問題を考える。 この設定の下では、ミニマックスリスクに対する情報理論の下限を導出する。 本稿では,2層ReLUニューラルネットワークに対して,提案手法と上界を拡張可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-23T02:39:04Z)
• Stochastic Bandits with Linear Constraints [69.757694218456]
  制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。 楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2020-06-17T22:32:19Z)

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

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