論文の概要: 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})$サンプルのみを必要とすることを証明している。
我々は,この上限値と推定器を用いて,バンディットモデル選択および治療効果試験におけるいくつかの応用の新規かつ改善された保証を得る。
関連論文リスト
- Stopping Bayesian Optimization with Probabilistic Regret Bounds [1.4141453107129403]
事実上の停止規則を$(epsilon, delta)$-criterionに置き換えることを検討する。
本研究では,後部から引き出された限られた数を用いて,この条件を実際に検証する方法を示す。
論文 参考訳(メタデータ) (2024-02-26T18:34:58Z) - Nearly Minimax Optimal Regret for Learning Linear Mixture Stochastic
Shortest Path [80.60592344361073]
線形混合遷移カーネルを用いた最短経路(SSP)問題について検討する。
エージェントは繰り返し環境と対話し、累積コストを最小化しながら特定の目標状態に到達する。
既存の作業は、イテレーションコスト関数の厳密な下限や、最適ポリシーに対する期待長の上限を仮定することが多い。
論文 参考訳(メタデータ) (2024-02-14T07:52:00Z) - 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) - Efficient Algorithms for Generalized Linear Bandits with Heavy-tailed
Rewards [40.99322897009357]
トランケーションと平均中央値に基づく2つの新しいアルゴリズムを提案する。
我々のトラニケーションベースのアルゴリズムは、既存のトラニケーションベースのアプローチと区別して、オンライン学習をサポートする。
我々のアルゴリズムは,$epsilon=1$の既存アルゴリズムと比較して,対数係数による後悔境界を改善する。
論文 参考訳(メタデータ) (2023-10-28T13:01:10Z) - 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) - Towards Instance-Optimal Offline Reinforcement Learning with Pessimism [34.54294677335518]
我々は、未知マルコフ決定過程(MDP)における報酬最大化ポリシーの学習を目標とするオフライン強化学習(オフラインRL)問題について検討する。
本研究では、適応悲観的値反復法(APVI)アルゴリズムを分析し、[Oleft(sum_h=1Hsum_s_h,a_hdpistar_h(s_h,a_h)sqrtfracmathrmmathrmVar_]とほぼ一致する準最適上限を導出する。
論文 参考訳(メタデータ) (2021-10-17T01:21:52Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。