論文の概要: Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
- arxiv url: http://arxiv.org/abs/2502.04004v1
- Date: Thu, 06 Feb 2025 12:03:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2025-02-07 14:31:57.916247
- Title: Near-optimal Regret Using Policy Optimization in Online MDPs with Aggregate Bandit Feedback
- Title（参考訳）: 帯域フィードバックを集約したオンラインMDPにおけるポリシー最適化を用いた準最適レグレット
- Authors: Tal Lancewicki, Yishay Mansour,
- Abstract要約: オンライン有限水平マルコフ決定過程を逆向きに変化した損失と総括的帯域幅フィードバック(フルバンド幅)を用いて研究する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
- 参考スコア（独自算出の注目度）: 49.84060509296641
- License:
- Abstract: We study online finite-horizon Markov Decision Processes with adversarially changing loss and aggregate bandit feedback (a.k.a full-bandit). Under this type of feedback, the agent observes only the total loss incurred over the entire trajectory, rather than the individual losses at each intermediate step within the trajectory. We introduce the first Policy Optimization algorithms for this setting. In the known-dynamics case, we achieve the first \textit{optimal} regret bound of $\tilde \Theta(H^2\sqrt{SAK})$, where $K$ is the number of episodes, $H$ is the episode horizon, $S$ is the number of states, and $A$ is the number of actions. In the unknown dynamics case we establish regret bound of $\tilde O(H^3 S \sqrt{AK})$, significantly improving the best known result by a factor of $H^2 S^5 A^2$.
- Abstract（参考訳）: オンライン有限ホリゾンマルコフ決定過程を逆向きに変化した損失と包帯フィードバック(すなわち全帯域)を用いて検討する。
この種のフィードバックの下では、エージェントは、軌跡内の各中間段階における個々の損失よりも、軌跡全体に生じる総損失のみを観察する。
この設定のための最初のポリシー最適化アルゴリズムを紹介します。
既知の力学の場合、最初の \textit{optimal} regret bound of $\tilde \Theta(H^2\sqrt{SAK})$, where $K$ is the number of episodes, $H$ is the episode horizon, $S$ is the number of state, $A$ is the number of action。
未知の力学の場合、$\tilde O(H^3 S \sqrt{AK})$の後悔境界を確立し、最もよく知られた結果を$H^2 S^5 A^2$の係数で著しく改善する。
関連論文リスト
- Improved Algorithm for Adversarial Linear Mixture MDPs with Bandit
Feedback and Unknown Transition [71.33787410075577]
線形関数近似,未知遷移,および逆損失を用いた強化学習について検討した。
我々は高い確率で$widetildeO(dsqrtHS3K + sqrtHSAK)$ regretを実現する新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-03-07T15:03:50Z) - Near-Minimax-Optimal Risk-Sensitive Reinforcement Learning with CVaR [58.40575099910538]
本研究は,リスク許容度が$tau$のCVaR(Conditional Value at Risk)の目的に着目し,リスクに敏感な強化学習(RL)について検討する。
ミニマックスCVaRの後悔率は$Omega(sqrttau-1AK)$で、$A$はアクションの数、$K$はエピソード数である。
我々は,このアルゴリズムが連続性仮定の下で$widetilde O(tau-1sqrtSAK)$の最適後悔を達成し,一般に近似することを示す。
論文 参考訳（メタデータ） (2023-02-07T02:22:31Z) - Double Thompson Sampling in Finite stochastic Games [10.559241770674724]
有限割引マルコフ決定プロセスの下での探索と利用のトレードオフ問題を考察する。
このような問題を解決するために、二重トンプソンサンプリング強化学習アルゴリズム(DTS)を提案する。
論文 参考訳（メタデータ） (2022-02-21T06:11:51Z) - Corralling a Larger Band of Bandits: A Case Study on Switching Regret
for Linear Bandits [99.86860277006318]
本稿では,一組の逆アルゴリズムを組み合わせ,学習することの問題点について考察する。
Agarwal et al. の CORRAL はこの目標を、$widetildeO(sqrtd S T)$ の残酷なオーバーヘッドで達成している。
この問題に触発されて、後悔のオーバーヘッドが百万ドルにしか依存しない大規模バンディットアルゴリズムのバンドを囲む新しいレシピを提案する。
論文 参考訳（メタデータ） (2022-02-12T21:55:44Z) - Gap-Dependent Unsupervised Exploration for Reinforcement Learning [40.990467706237396]
タスクに依存しない強化学習のための効率的なアルゴリズムを提案する。
このアルゴリズムは1/epsilon cdot (H3SA / rho + H4 S2 A) の$widetildemathcalOのみを探索する。
情報理論上、この境界は$rho Theta (1/(HS))$と$H>1$に対してほぼ厳密であることを示す。
論文 参考訳（メタデータ） (2021-08-11T20:42:46Z) - Nearly Horizon-Free Offline Reinforcement Learning [97.36751930393245]
S$状態、$A$アクション、計画的地平$H$で、エピソードな時間同質なMarkov決定プロセスに関するオフライン強化学習を再考する。
経験的MDPを用いた評価と計画のための,約$H$自由なサンプル複雑性境界の最初の集合を得る。
論文 参考訳（メタデータ） (2021-03-25T18:52:17Z) - Minimax Regret for Stochastic Shortest Path [63.45407095296692]
我々は、エージェントが最小の総予想コストで目標状態に達する必要がある最短パス(SSP)問題を研究します。
この設定に対するminimaxの後悔は、$widetilde O(B_star sqrt|S| |A|K)$であり、$B_star$は任意の状態から最適なポリシーの予想コストに拘束されることを示しています。
本アルゴリズムは, 有限水平MDPにおける強化学習の新たな削減を基礎として, エピソードごとのインタイム動作を行う。
論文 参考訳（メタデータ） (2021-03-24T10:11:49Z) - Finding the Stochastic Shortest Path with Low Regret: The Adversarial
Cost and Unknown Transition Case [29.99619764839178]
敵の費用と未知の遷移を伴う最短経路問題に対して,大きな進展をみせている。
具体的には、全情報設定を後悔する$widetildeO(sqrtS3A2DT_star K)を実現するアルゴリズムを開発する。
私たちはまた、最も難しい組み合わせとして、敵のコストによる盗聴フィードバックと未知の移行を最初に検討しています。
論文 参考訳（メタデータ） (2021-02-10T06:33:04Z) - Lazy OCO: Online Convex Optimization on a Switching Budget [34.936641201844054]
我々は、オンライン凸最適化の変形について研究し、プレイヤーは、T$ラウンドを通して、最大$S$で決定を切り替えることを許されている。
離散的な決定セットの事前の作業や、より最近の連続的な設定では、適応的な逆数でのみ、同様の問題が解決されている。
論文 参考訳（メタデータ） (2021-02-07T14:47:19Z) - Learning Adversarial Markov Decision Processes with Delayed Feedback [45.86354980347581]
私たちは、未知の移行、逆転的なコストの変動、制限のない遅延フィードバックを備えた典型的マルコフ決定プロセス(MDP)におけるオンライン学習を検討します。
本論文では,$widetilde O ( sqrtK + sqrtD )$ のほぼ最適高確率後悔を実現するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-12-29T16:47:42Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。