論文の概要: Tractable Optimality in Episodic Latent MABs

• arxiv url: http://arxiv.org/abs/2210.03528v1
• Date: Wed, 5 Oct 2022 22:53:46 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-10 13:33:03.627277
• Title: Tractable Optimality in Episodic Latent MABs
• Title（参考訳）: 表在性MABのトラクタブル最適性
• Authors: Jeongyeol Kwon, Yonathan Efroni, Constantine Caramanis, Shie Mannor
• Abstract要約: 我々は、エージェントが時間ステップ$H$のエピソードのために環境と対話する、M$遅延コンテキストを持つマルチアームバンディット問題を考える。 エピソードの長さによっては、学習者は遅れた文脈を正確に見積もることができないかもしれない。 我々は、$O(textttpoly(A) + textttpoly(M,H)min(M,H))$インタラクションを用いて、ほぼ最適なポリシーを確実に学習する手順を設計する。
• 参考スコア（独自算出の注目度）: 75.17357040707347
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider a multi-armed bandit problem with $M$ latent contexts, where an agent interacts with the environment for an episode of $H$ time steps. Depending on the length of the episode, the learner may not be able to estimate accurately the latent context. The resulting partial observation of the environment makes the learning task significantly more challenging. Without any additional structural assumptions, existing techniques to tackle partially observed settings imply the decision maker can learn a near-optimal policy with $O(A)^H$ episodes, but do not promise more. In this work, we show that learning with {\em polynomial} samples in $A$ is possible. We achieve this by using techniques from experiment design. Then, through a method-of-moments approach, we design a procedure that provably learns a near-optimal policy with $O(\texttt{poly}(A) + \texttt{poly}(M,H)^{\min(M,H)})$ interactions. In practice, we show that we can formulate the moment-matching via maximum likelihood estimation. In our experiments, this significantly outperforms the worst-case guarantees, as well as existing practical methods.
• Abstract（参考訳）: エージェントが$h$の時間ステップのエピソードのために環境と対話する、$m$の潜在コンテキストを持つマルチアームのバンディット問題を考える。 エピソードの長さによっては、学習者は潜在する文脈を正確に推定できない可能性がある。 結果として環境の部分的な観察が、学習タスクを著しく難しくする。 構造的な仮定がなければ、部分的に観察された設定に対処する既存の手法は、意思決定者が$O(A)^H$のエピソードでほぼ最適のポリシーを学習できることを意味するが、それ以上は約束しない。 本研究では,$a$ の条件で {\em polynomial} サンプルを用いた学習が可能であることを示す。 実験設計の技術を用いてこれを実現する。 次に、メソッド・オブ・モーメントのアプローチを通じて、$o(\texttt{poly}(a) + \texttt{poly}(m,h)^{\min(m,h)}) の相互作用で最適に近いポリシーを確実に学習する手順を設計する。 実際,最大推定値を用いてモーメントマッチングを定式化できることが示される。 我々の実験では、これは既存の実用的な方法と同様に最悪のケースの保証を著しく上回る。

関連論文リスト

• Narrowing the Gap between Adversarial and Stochastic MDPs via Policy Optimization [11.11876897168701]
  本稿では,次数$tildemathcalO(mathrmpoly(H)sqrtSAT)$の残差を求めるアルゴリズムを提案する。 提案したアルゴリズムと分析は、占有対策によって与えられる典型的なツールを完全に回避する。
  論文  参考訳（メタデータ） (2024-07-08T08:06:45Z)
• Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge [0.704590071265998]
  オンラインQ-ラーニング手法のサンプル複雑性について,動的知識が利用可能であったり,効率的に学習できたりした場合に検討する。 我々は,$f$の完全知識の下で,$tildemathcalO(textPoly(H)sqrtSAT)$ regretを達成する楽観的なQ-ラーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-12-19T19:53:58Z)
• Adversarial Online Multi-Task Reinforcement Learning [12.421997449847153]
  対戦型オンラインマルチタスク強化学習環境について考察する。 K$の各エピソードにおいて、学習者は未知のタスクをM$未知有限ホライゾン MDP モデルの有限集合から与えられる。 学習者の目的は,各課題に対する最適方針に関して,その後悔を一般化することである。
  論文  参考訳（メタデータ） (2023-01-11T02:18:26Z)
• Reaching Goals is Hard: Settling the Sample Complexity of the Stochastic Shortest Path [106.37656068276902]
  本稿では,最短経路(SSP)問題において,$epsilon$-optimal Policyを学習する際のサンプル複雑性について検討する。 学習者が生成モデルにアクセスできる場合、複雑性境界を導出する。 我々は、$S$状態、$A$アクション、最小コスト$c_min$、およびすべての状態に対する最適ポリシーの最大期待コストを持つ最悪のSSPインスタンスが存在することを示す。
  論文  参考訳（メタデータ） (2022-10-10T18:34:32Z)
• Reward-Mixing MDPs with a Few Latent Contexts are Learnable [75.17357040707347]
  報酬混合マルコフ決定過程(RMMDP)におけるエピソード強化学習の検討 我々のゴールは、そのようなモデルにおける時間段階の累積報酬をほぼ最大化する、ほぼ最適に近いポリシーを学ぶことである。
  論文  参考訳（メタデータ） (2022-10-05T22:52:00Z)
• Minimax Optimal Online Imitation Learning via Replay Estimation [47.83919594113314]
  本稿では,この経験的分散を低減するために,リプレイ推定手法を提案する。 提案手法では, min(H3/2 / N, H / sqrtN$)$ 依存度を最適に$widetildeO に設定する。
  論文  参考訳（メタデータ） (2022-05-30T19:29:56Z)
• Agnostic Reinforcement Learning with Low-Rank MDPs and Rich Observations [79.66404989555566]
  我々は、リッチな観測空間を持つより現実的な非依存的RLの設定と、近似的ポリシーを含まないような固定されたポリシーのクラス$Pi$を考える。 我々は,MDPの階数$d$の誤差が有界な設定のためのアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-06-22T03:20:40Z)
• Online Apprenticeship Learning [58.45089581278177]
  見習い学習(AL)では、コスト関数にアクセスせずにマルコフ決定プロセス(MDP)が与えられます。 目標は、事前に定義されたコスト関数のセットで専門家のパフォーマンスに一致するポリシーを見つけることです。 ミラー下降型ノンレグレットアルゴリズムを2つ組み合わせることで,OAL問題を効果的に解くことができることを示す。
  論文  参考訳（メタデータ） (2021-02-13T12:57:51Z)

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

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