論文の概要: Episodic Bandits with Stochastic Experts
- arxiv url: http://arxiv.org/abs/2107.03263v1
- Date: Wed, 7 Jul 2021 14:58:14 GMT
- ステータス: 処理完了
- システム内更新日: 2021-07-08 13:59:15.684830
- Title: Episodic Bandits with Stochastic Experts
- Title(参考訳): 確率的専門家とエピソードバンド
- Authors: Nihal Sharma, Soumya Basu, Karthikeyan Shanmugam, Sanjay Shakkottai
- Abstract要約: 本研究では,エージェントがグラフ構造化環境におけるノードのソフトコントロールを,一連の専門家ポリシーを通じて与える,バンディット問題のバージョンについて検討する。
本稿では,エージェントが専門的方針や文脈分布の変化について知識を持っていない場合に,経験的分散に基づくUPBアルゴリズムを導入する。
我々は、$tildeO(E(N+1) + fracNsqrtET2)$からのブートストラップが、$tildeO(EN)$を必要とせずに後悔する結果をもたらすことを示す。
- 参考スコア(独自算出の注目度): 39.677482864848365
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study a version of the contextual bandit problem where an agent is given
soft control of a node in a graph-structured environment through a set of
stochastic expert policies. The agent interacts with the environment over
episodes, with each episode having different context distributions; this
results in the `best expert' changing across episodes. Our goal is to develop
an agent that tracks the best expert over episodes. We introduce the Empirical
Divergence-based UCB (ED-UCB) algorithm in this setting where the agent does
not have any knowledge of the expert policies or changes in context
distributions. With mild assumptions, we show that bootstrapping from
$\tilde{O}(N\log(NT^2\sqrt{E}))$ samples results in a regret of
$\tilde{O}(E(N+1) + \frac{N\sqrt{E}}{T^2})$. If the expert policies are known
to the agent a priori, then we can improve the regret to $\tilde{O}(EN)$
without requiring any bootstrapping. Our analysis also tightens pre-existing
logarithmic regret bounds to a problem-dependent constant in the non-episodic
setting when expert policies are known. We finally empirically validate our
findings through simulations.
- Abstract(参考訳): 本研究では,エージェントがグラフ構造化環境におけるノードのソフトコントロールを,確率的専門家ポリシーの集合を通じて与える文脈的帯域問題のバージョンについて検討する。
エージェントはエピソードを通して環境と対話し、それぞれのエピソードは異なるコンテキストの分布を持つ。
私たちの目標は、エピソードを通して最高のエキスパートを追跡するエージェントを開発することです。
本稿では,エージェントが専門家の方針や文脈分布の変化について何も知らない環境で,経験的ダイバージェンスに基づくucb(ed-ucb)アルゴリズムを導入する。
軽度の仮定で、$\tilde{O}(N\log(NT^2\sqrt{E}))$サンプルからブートストラッピングすると、$\tilde{O}(E(N+1) + \frac{N\sqrt{E}}{T^2})$の後悔が生じる。
専門家のポリシーがエージェントにa prioriを知っていれば、ブートストラップを必要とせずに$\tilde{O}(EN)$への後悔を改善することができる。
分析は,専門家の方針が分かっている場合の非正規設定における問題依存定数に対して,既存の対数的後悔境界を厳格化する。
最終的にシミュレーションにより結果が実証的に検証された。
関連論文リスト
- Probably Anytime-Safe Stochastic Combinatorial Semi-Bandits [81.60136088841948]
本稿では,時間軸における後悔を最小限に抑えるアルゴリズムを提案する。
提案アルゴリズムは,レコメンデーションシステムや交通機関などの分野に適用可能である。
論文 参考訳(メタデータ) (2023-01-31T03:49:00Z) - Tractable Optimality in Episodic Latent MABs [75.17357040707347]
我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。
エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。
我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
論文 参考訳(メタデータ) (2022-10-05T22:53:46Z) - Toward the Fundamental Limits of Imitation Learning [29.87139380803829]
シミュレーション学習(IL)は、実演のみを与えられた逐次的な意思決定問題において、専門家の政策の振る舞いを模倣することを目的としている。
まず,学習者が事前に$N$のエキスパートトラジェクトリのデータセットを提供して,MDPと対話できないような設定について検討する。
可能な限り専門家を模倣するポリシーは、専門家が任意のポリシーに従う場合でも、専門家の値と比較すると、$lesssim frac|mathcalS| H2 log (N)N$ suboptimalであることを示す。
論文 参考訳(メタデータ) (2020-09-13T12:45:52Z) - Stochastic Shortest Path with Adversarially Changing Costs [57.90236104782219]
最短経路 (SSP) は計画と制御においてよく知られた問題である。
また, 時間とともにコストの逆変化を考慮に入れた逆SSPモデルを提案する。
我々は、この自然な逆SSPの設定を最初に検討し、それに対するサブ線形後悔を得る。
論文 参考訳(メタデータ) (2020-06-20T12:10:35Z) - Stochastic Bandits with Linear Constraints [69.757694218456]
制約付き文脈線形帯域設定について検討し、エージェントの目標は一連のポリシーを作成することである。
楽観的悲観的線形帯域(OPLB)と呼ばれる,この問題に対する高信頼束縛アルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-17T22:32:19Z) - Simultaneously Learning Stochastic and Adversarial Episodic MDPs with
Known Transition [38.28925339231888]
我々は,世界最良保証付きの最初のアルゴリズムを開発した。
損失が逆ならば、$mathcalO(log T)$ regretを達成します。
より一般的には、中間設定で $tildemathcalO(sqrtC)$ regret を達成する。
論文 参考訳(メタデータ) (2020-06-10T01:59:34Z) - Near-optimal Regret Bounds for Stochastic Shortest Path [63.029132134792555]
最短経路 (SSP) は計画と制御においてよく知られた問題であり、エージェントは最小の総コストで目標状態に到達する必要がある。
任意の学習アルゴリズムは、最悪の場合、少なくとも$Omega(B_star sqrt|S| |A|K)$後悔しなければならない。
論文 参考訳(メタデータ) (2020-02-23T09:10:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。