論文の概要: Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
- arxiv url: http://arxiv.org/abs/2603.03480v1
- Date: Tue, 03 Mar 2026 19:52:24 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-03-05 21:29:15.070957
- Title: Minimax Optimal Strategy for Delayed Observations in Online Reinforcement Learning
- Title（参考訳）: オンライン強化学習における遅延観測のためのミニマックス最適戦略
- Authors: Harin Lee, Kevin Jamieson,
- Abstract要約: 本研究では,エージェントが無作為な時間経過後に現在の状態を観察する,遅延状態観察による強化学習について検討する。
本稿では,拡張法と高信頼度バウンドアプローチを組み合わせたアルゴリズムを提案する。
- 参考スコア（独自算出の注目度）: 8.140056861479176
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We study reinforcement learning with delayed state observation, where the agent observes the current state after some random number of time steps. We propose an algorithm that combines the augmentation method and the upper confidence bound approach. For tabular Markov decision processes (MDPs), we derive a regret bound of $\tilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})$, where $S$ and $A$ are the cardinalities of the state and action spaces, $H$ is the time horizon, $K$ is the number of episodes, and $D_{\max}$ is the maximum length of the delay. We also provide a matching lower bound up to logarithmic factors, showing the optimality of our approach. Our analytical framework formulates this problem as a special case of a broader class of MDPs, where their transition dynamics decompose into a known component and an unknown but structured component. We establish general results for this abstract setting, which may be of independent interest.
- Abstract（参考訳）: 本研究では,エージェントが無作為な時間経過後に現在の状態を観察する,遅延状態観察による強化学習について検討する。
本稿では,拡張法と高信頼度バウンドアプローチを組み合わせたアルゴリズムを提案する。
表式マルコフ決定プロセス(MDPs)では、$\tilde{\mathcal{O}}(H \sqrt{D_{\max} SAK})$, ここで、$S$と$A$は状態と作用空間の濃度、$H$は時間軸、$K$はエピソード数、$D_{\max}$は遅延の最大値である。
また、対数的要因までの境界が一致し、アプローチの最適性を示す。
我々の分析フレームワークは、この問題を、その遷移力学が既知のコンポーネントと未知だが構造化されたコンポーネントに分解される、より広い種類のMDPの特殊なケースとして定式化している。
この抽象的な設定に対する一般的な結果を確立し、これは独立した関心を持つかもしれない。
関連論文リスト
- Asymptotically optimal reinforcement learning in Block Markov Decision Processes [0.22835610890984168]
強化学習 (Reinforcement Learning, RL) は、指数関数的に大きな状態と行動空間を持つ実世界の多くの環境では実用的ではない。
クラスタリングを明示的に活用する残念な分析を行い、正確な潜在状態推定が学習を効果的に高速化することを示した。
このアルゴリズムは、クラスタリングの影響を受けやすいBMDPの大規模なクラスで$O(sqrtT+n2)$となる後悔を実現する。
論文 参考訳（メタデータ） (2025-10-15T16:54:06Z) - Reinforcement Learning from Adversarial Preferences in Tabular MDPs [62.73758165845971]
我々は,敵対的嗜好を持つエピソードマルコフ決定プロセス(MDP)の新たな枠組みを導入する。
PbMDP では、標準的なエピソード MDP とは異なり、学習者は2つの候補アーム間の好みを観察する。
我々は、既知遷移の下で、T2/3$という残差境界を達成するアルゴリズムを開発する。
論文 参考訳（メタデータ） (2025-07-15T20:19:32Z) - Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation [8.274693573069442]
多項ロジスティック(MNL)関数近似を用いた強化学習について検討した。
頻繁な後悔の保証を有するランダムな探索を伴う確率的効率のアルゴリズムを提案する。
数値実験により提案アルゴリズムの優れた性能を示す。
論文 参考訳（メタデータ） (2024-05-30T15:39:19Z) - Reinforcement Learning in a Birth and Death Process: Breaking the
Dependence on the State Space [0.0]
我々は、出生・死亡構造を有するMDPにおける未報告の強化学習の後悔を再考する。
本研究の結果から,従来の学習アルゴリズム sc Ucrl2 のやや遅れたバージョンに対する後悔は,実際には $tildemathcalO(sqrtEAT)$ で表される。
論文 参考訳（メタデータ） (2023-02-21T13:28:37Z) - Horizon-Free Reinforcement Learning in Polynomial Time: the Power of
Stationary Policies [88.75843804630772]
我々は既存の境界に対して,$Oleft(mathrmpoly(S,A,log K)sqrtKright)を後悔するアルゴリズムを設計する。
この結果は、定常政策の近似力、安定性、および濃度特性を確立する新しい構造補題の列に依存している。
論文 参考訳（メタデータ） (2022-03-24T08:14:12Z) - 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) - Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function
Approximation [92.3161051419884]
我々は、敵対的な報酬と完全な情報フィードバックで有限正方体エピソディックマルコフ決定プロセスのための強化学習を研究します。
我々は、$tildeO(dHsqrtT)$ regretを達成できることを示し、$H$はエピソードの長さである。
また、対数因子までの$tildeOmega(dHsqrtT)$の値が一致することを証明する。
論文 参考訳（メタデータ） (2021-02-17T18:54:08Z) - Provably Efficient Reinforcement Learning for Discounted MDPs with
Feature Mapping [99.59319332864129]
本稿では,割引決定(MDP)のための強化学習について検討する。
本稿では,特徴写像を利用した新しいアルゴリズムを提案し,$tilde O(dsqrtT/ (1-gamma)2)$ regretを求める。
以上の結果から,提案した強化学習アルゴリズムは,最大1-γ-0.5$の係数でほぼ最適であることが示唆された。
論文 参考訳（メタデータ） (2020-06-23T17:08:54Z) - Upper Confidence Primal-Dual Reinforcement Learning for CMDP with
Adversarial Loss [145.54544979467872]
マルコフ決定過程(CMDP)に対するオンライン学習の検討
本稿では,遷移モデルから標本化した軌跡のみを必要とする,新しいEmphupper confidence primal-dualアルゴリズムを提案する。
我々の分析では、ラグランジュ乗算過程の新たな高確率ドリフト解析を、高信頼強化学習の記念後悔解析に組み入れている。
論文 参考訳（メタデータ） (2020-03-02T05:02:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。