論文の概要: Risk and optimal policies in bandit experiments
- arxiv url: http://arxiv.org/abs/2112.06363v1
- Date: Mon, 13 Dec 2021 00:41:19 GMT
- ステータス: 処理完了
- システム内更新日: 2021-12-14 18:55:46.475405
- Title: Risk and optimal policies in bandit experiments
- Title(参考訳): バンディット実験におけるリスクと最適政策
- Authors: Karun Adusumilli
- Abstract要約: 本稿では,バンディット実験の意思決定理論解析について述べる。
バンディット設定は動的プログラミング問題に対応するが、これを直接解くことは一般的に不可能である。
通常分散報酬の場合、最小ベイズリスクは非線形二階偏微分方程式の解として特徴づけられる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper provides a decision theoretic analysis of bandit experiments. The
bandit setting corresponds to a dynamic programming problem, but solving this
directly is typically infeasible. Working within the framework of diffusion
asymptotics, we define a suitable notion of asymptotic Bayes risk for bandit
settings. For normally distributed rewards, the minimal Bayes risk can be
characterized as the solution to a nonlinear second-order partial differential
equation (PDE). Using a limit of experiments approach, we show that this PDE
characterization also holds asymptotically under both parametric and
non-parametric distribution of the rewards. The approach further describes the
state variables it is asymptotically sufficient to restrict attention to, and
therefore suggests a practical strategy for dimension reduction. The upshot is
that we can approximate the dynamic programming problem defining the bandit
setting with a PDE which can be efficiently solved using sparse matrix
routines. We derive near-optimal policies from the numerical solutions to these
equations. The proposed policies substantially dominate existing methods such
Thompson sampling. The framework also allows for substantial generalizations to
the bandit problem such as time discounting and pure exploration motives.
- Abstract(参考訳): 本稿では,バンディット実験の決定論的解析について述べる。
バンディット設定は動的プログラミング問題に対応するが、これを直接解くことは一般的に不可能である。
拡散漸近の枠組みの中で作業し、バンドイット設定に対する漸近ベイズリスクの適切な概念を定義する。
通常分散報酬の場合、最小ベイズリスクは非線形二階偏微分方程式(PDE)の解として特徴づけられる。
実験手法の限界を用いて、このPDE特性は、報酬のパラメトリック分布と非パラメトリック分布の両方において漸近的に保持されることを示す。
このアプローチはさらに、注意を制限するのに漸近的に十分である状態変数を記述し、従って次元減少のための実用的な戦略を提案する。
アップショットは、バンドレート設定を定義する動的プログラミング問題を、スパース行列ルーチンを用いて効率的に解けるPDEで近似できるということである。
これらの方程式に対する数値解から準最適ポリシーを導出する。
提案手法はトンプソンサンプリングのような既存の手法を実質的に支配している。
このフレームワークは、時間ディスカウントや純粋な探検動機など、バンディット問題の実質的な一般化も可能にする。
関連論文リスト
- Towards Principled, Practical Policy Gradient for Bandits and Tabular MDPs [9.58750210024265]
バンディットとマルコフ決定過程(MDP)に対する(確率的)ソフトマックスポリシー勾配(PG)法について検討する。
提案アルゴリズムは,技術結果と類似した理論的保証を提供するが,オラクルのような量の知識は必要としないことを示す。
マルチアームバンディット設定の場合,提案手法は明示的な探索や報奨ギャップの知識,報奨分布,ノイズを必要としない理論的なPGアルゴリズムを実現する。
論文 参考訳(メタデータ) (2024-05-21T18:12:39Z) - Model-Based Epistemic Variance of Values for Risk-Aware Policy Optimization [59.758009422067]
モデルベース強化学習における累積報酬に対する不確実性を定量化する問題を考察する。
我々は、解が値の真後分散に収束する新しい不確実性ベルマン方程式(UBE)を提案する。
本稿では,リスク・サーキングとリスク・アバース・ポリシー最適化のいずれにも適用可能な汎用ポリシー最適化アルゴリズムQ-Uncertainty Soft Actor-Critic (QU-SAC)を導入する。
論文 参考訳(メタデータ) (2023-12-07T15:55:58Z) - Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳(メタデータ) (2023-10-01T01:37:02Z) - Indexability is Not Enough for Whittle: Improved, Near-Optimal
Algorithms for Restless Bandits [30.532795983761314]
本研究では,複数の行動を伴うレスレス・マルチアーム・バンディット(RMAB)の計画問題について検討する。
まず、Whittleインデックスポリシーは、シンプルで実用的な設定で失敗する可能性があることを示す。
次に,平均場法に基づく代替計画アルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-10-31T19:35:15Z) - Risk-aware linear bandits with convex loss [0.0]
提案手法は, 線形帯域幅の一般化に類似した, 最適リスク認識動作を学習するための楽観的 UCB アルゴリズムを提案する。
このアプローチではアルゴリズムの各ラウンドで凸問題を解く必要があり、オンライン勾配降下法によって得られる近似解のみを許すことで緩和することができる。
論文 参考訳(メタデータ) (2022-09-15T09:09:53Z) - Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
可分バナッハ空間上で定義された収縮作用素の定点を推定する問題について検討する。
演算子欠陥と推定誤差の両方に対して漸近的でない境界を確立する。
論文 参考訳(メタデータ) (2022-01-21T02:46:57Z) - A Unifying Theory of Thompson Sampling for Continuous Risk-Averse
Bandits [91.3755431537592]
本稿では,多腕バンディット問題に対するリスク-逆トンプソンサンプリングアルゴリズムの解析を統一する。
大規模偏差理論における収縮原理を用いることで、連続リスク汎関数に対する新しい濃度境界が証明される。
リスク関数の幅広いクラスと「ニセ」関数が連続性条件を満たすことを示す。
論文 参考訳(メタデータ) (2021-08-25T17:09:01Z) - Nearly Dimension-Independent Sparse Linear Bandit over Small Action
Spaces via Best Subset Selection [71.9765117768556]
本研究では,高次元線形モデルの下での文脈的帯域問題について考察する。
この設定は、パーソナライズされたレコメンデーション、オンライン広告、パーソナライズされた医療など、不可欠な応用を見出す。
本稿では,最適部分集合選択法を用いて2重成長エポックを推定する手法を提案する。
論文 参考訳(メタデータ) (2020-09-04T04:10:39Z) - Thompson Sampling Algorithms for Mean-Variance Bandits [97.43678751629189]
我々は平均分散MABのためのトンプソンサンプリング型アルゴリズムを開発した。
我々はまた、ガウシアンとベルヌーイの盗賊に対する包括的後悔の分析も提供する。
我々のアルゴリズムは、全てのリスク許容度に対して既存のLCBベースのアルゴリズムを著しく上回っている。
論文 参考訳(メタデータ) (2020-02-01T15:33:50Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。