論文の概要: Variational Bayesian Optimistic Sampling
- arxiv url: http://arxiv.org/abs/2110.15688v1
- Date: Fri, 29 Oct 2021 11:28:29 GMT
- ステータス: 処理完了
- システム内更新日: 2021-11-01 19:39:14.147977
- Title: Variational Bayesian Optimistic Sampling
- Title(参考訳): 変分ベイズ最適化サンプリング
- Authors: Brendan O'Donoghue and Tor Lattimore
- Abstract要約: エージェントが探索と搾取のバランスをとる必要があるオンラインシーケンシャルな意思決定問題を考える。
我々は、多腕バンディットの場合、トンプソンサンプリングポリシーを含むベイズ楽観的な政策の集合を導出する。
楽観的な集合におけるポリシーを生成するアルゴリズムは、$T$ラウンド後の$A$アクションの問題に対して$tilde O(sqrtAT)$ Bayesian regretを楽しんでいることが示される。
- 参考スコア(独自算出の注目度): 43.130465039780084
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We consider online sequential decision problems where an agent must balance
exploration and exploitation. We derive a set of Bayesian `optimistic' policies
which, in the stochastic multi-armed bandit case, includes the Thompson
sampling policy. We provide a new analysis showing that any algorithm producing
policies in the optimistic set enjoys $\tilde O(\sqrt{AT})$ Bayesian regret for
a problem with $A$ actions after $T$ rounds. We extend the regret analysis for
optimistic policies to bilinear saddle-point problems which include zero-sum
matrix games and constrained bandits as special cases. In this case we show
that Thompson sampling can produce policies outside of the optimistic set and
suffer linear regret in some instances. Finding a policy inside the optimistic
set amounts to solving a convex optimization problem and we call the resulting
algorithm `variational Bayesian optimistic sampling' (VBOS). The procedure
works for any posteriors, \ie, it does not require the posterior to have any
special properties, such as log-concavity, unimodality, or smoothness. The
variational view of the problem has many useful properties, including the
ability to tune the exploration-exploitation tradeoff, add regularization,
incorporate constraints, and linearly parameterize the policy.
- Abstract(参考訳): エージェントが探索と搾取のバランスをとる必要があるオンラインシーケンシャルな意思決定問題を考える。
我々は、確率的マルチアームバンディットの場合、トンプソンサンプリングポリシーを含むベイズ的「最適化」ポリシーのセットを導出する。
楽観的なセットでポリシーを生成するアルゴリズムは、$t$ラウンド後の$a$アクションの問題に対して$\tilde o(\sqrt{at})$ bayesian regretを享受できることを示す新しい分析を提供する。
楽観的政策に対する後悔分析を,ゼロサム行列ゲームや制約付きバンディットを特別な場合として含む双線形saddle-point問題へと拡張する。
この場合、トンプソンサンプリングは楽観的な集合の外側でポリシーを生成でき、ある事例では線形な後悔を味わうことができる。
楽観的集合内のポリシーを見つけることは凸最適化問題の解法に相当し、その結果のアルゴリズムを'変数ベイズ楽観的サンプリング' (VBOS) と呼ぶ。
この手順は、任意の後肢に対して作用するが、後肢は、ログコンベビティ、ユニモダリティ、滑らかさなどの特別な性質を持つ必要はない。
問題の変動ビューには、探索・探索トレードオフの調整、正規化の追加、制約の統合、ポリシーの線形パラメータ化など、多くの有用な特性がある。
関連論文リスト
- Thompson Exploration with Best Challenger Rule in Best Arm
Identification [66.33448474838342]
本稿では,バンドイットフレームワークにおける固定信頼度最良腕識別問題について検討する。
我々は、トンプソンサンプリングと、ベストチャレンジャールールとして知られる計算効率の良いアプローチを組み合わせた新しいポリシーを提案する。
論文 参考訳(メタデータ) (2023-10-01T01:37:02Z) - Low-Switching Policy Gradient with Exploration via Online Sensitivity
Sampling [23.989009116398208]
一般非線形関数近似を用いた低スイッチングサンプリング効率ポリシ最適化アルゴリズム LPO を設計する。
提案アルゴリズムは,$widetildeO(fractextpoly(d)varepsilon3)$サンプルのみを用いて,$varepsilon$-optimal Policyを得る。
論文 参考訳(メタデータ) (2023-06-15T23:51:46Z) - Autoregressive Bandits [58.46584210388307]
本稿では,オンライン学習環境であるAutoregressive Banditsを提案する。
報酬プロセスの軽微な仮定の下では、最適ポリシーを便利に計算できることが示される。
次に、新しい楽観的後悔最小化アルゴリズム、すなわちAutoRegressive Upper Confidence Bound (AR-UCB)を考案し、$widetildemathcalO left( frac(k+1)3/2sqrtnT (1-G)のサブ線形後悔を被る。
論文 参考訳(メタデータ) (2022-12-12T21:37:36Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
逆強化学習(IRL)は報酬関数と関連する最適ポリシーを回復することを目的としている。
IRLの多くのアルゴリズムは本質的にネスト構造を持つ。
我々は、報酬推定精度を損なわないIRLのための新しいシングルループアルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-10-04T17:13:45Z) - Finite-Sample Analysis of Off-Policy Natural Actor-Critic Algorithm [4.932130498861987]
重要度サンプリングに基づく自然アクタ-クリティック(nac)アルゴリズムのオフポリシー変種に対する有限サンプル収束保証を提供する。
このアルゴリズムは、ステップの適切な選択の下で$mathcalo(epsilon-3log2(1/epsilon)$のサンプル複雑性を持つ大域的最適ポリシーに収束する。
論文 参考訳(メタデータ) (2021-02-18T13:22:59Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
我々は,事前の報奨を後悔する$tilde O(sqrtS2 A H4 K)を定め,楽観的な信頼領域ポリシー最適化(TRPO)アルゴリズムを提案する。
我々の知る限り、この2つの結果は、未知の遷移と帯域幅フィードバックを持つポリシー最適化アルゴリズムにおいて得られた最初のサブ線形後悔境界である。
論文 参考訳(メタデータ) (2020-02-19T15:41:18Z) - Differentiable Bandit Exploration [38.81737411000074]
我々は、$mathcalP$からサンプルを使って未知のディストリビューション$mathcalP$についてそのようなポリシーを学ぶ。
我々のアプローチはメタラーニングの形式であり、その形式について強い仮定をすることなく$mathcalP$のプロパティを利用する。
論文 参考訳(メタデータ) (2020-02-17T05:07:35Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。