Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions

• URL: http://arxiv.org/abs/2606.31769v1
• Date: Tue, 30 Jun 2026 14:54:34 GMT
• Title: Policy Optimization Achieves Data-Dependent Regret Bounds in MDPs with Unknown Transitions
• Abstract summary: Policy optimization can adapt to both adversarial and losses with first-order, second-order, and path-length bounds.<n>We develop a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions.
• Score: 15.092125124258592
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study policy optimization for online episodic tabular Markov decision processes with unknown transition kernels, aiming for best-of-both-worlds guarantees together with data-dependent regret bounds. Recent work (Dann et al., 2023; Li et al., 2026) has shown that policy optimization can adapt to both adversarial and stochastic losses with first-order, second-order, and path-length bounds, but only under known transitions, leaving open whether such data-dependent guarantees are achievable by policy optimization when the transition kernel is unknown. We resolve this by developing a new algorithm based on optimistic follow-the-regularized-leader that attains these guarantees under unknown transitions. The key ingredient is a new design of optimistic $Q$-function estimators together with a data-dependent transition bonus that controls estimator bias through the loss-prediction error. Our analysis further identifies an unavoidable transition-dependent complexity term that captures the intrinsic cost of estimating the transition kernel. As a result, we obtain first-order, second-order, and path-length bounds with the transition-dependent complexity term while simultaneously achieving gap-dependent $\mathrm{polylog}(T)$ regret in the stochastic regime.

Related papers

• Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses [0.8984888893275712]
  We introduce and run with a new class of policies, which we call weighted LogSumExp softmax policies.<n>Two novel algorithmic components -- periodic policy mixing and a regularized dual update -- allow us to effectively control both the covering number and the dual variable.
  arXiv  Detail & Related papers  (2026-05-12T05:02:02Z)
• Near-Optimal Primal-Dual Algorithm for Learning Linear Mixture CMDPs with Adversarial Rewards [0.8984888893275712]
  We study safe reinforcement learning in finite-horizon linear mixture constrained Markov decision processes.<n>We propose a primal-dual policy optimization algorithm that achieves regret and constraint violation bounds.<n>This is the first provably efficient algorithm for linear mixture CMDPs with adversarial rewards.
  arXiv  Detail & Related papers  (2026-03-29T21:51:33Z)
• Data- and Variance-dependent Regret Bounds for Online Tabular MDPs [15.092125124258592]
  We develop best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the regime.<n>For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon.
  arXiv  Detail & Related papers  (2026-02-02T10:09:29Z)
• SGD with Dependent Data: Optimal Estimation, Regret, and Inference [3.038061705362137]
  gradient descent (SGD) is shown to accommodate both independent and dependent information under a broad class of stepsize schedules and exploration rate schemes.<n>We show that SGD simultaneously achieves statistically optimal estimation error and regret, extending and improving existing results.<n>For online sparse regression, we develop a new SGD-based algorithm that uses only $d$ units of storage and requires $O(d)$ flops per iteration.
  arXiv  Detail & Related papers  (2026-01-04T04:52:11Z)
• Generalized Linear Bandits: Almost Optimal Regret with One-Pass Update [70.38810219913593]
  We study the generalized linear bandit (GLB) problem, a contextual multi-armed bandit framework that extends the classical linear model by incorporating a non-linear link function.<n>GLBs are widely applicable to real-world scenarios, but their non-linear nature introduces significant challenges in achieving both computational and statistical efficiency.<n>We propose a jointly efficient algorithm that attains a nearly optimal regret bound with $mathcalO(1)$ time and space complexities per round.
  arXiv  Detail & Related papers  (2025-07-16T02:24:21Z)
• Robust Offline Reinforcement Learning with Linearly Structured f-Divergence Regularization [11.739526562075339]
  The Robust Regularized Markov Decision Process (RRMDP) is proposed to learn policies robust to dynamics shifts by adding regularization to the transition dynamics in the value function.<n>We develop the Robust Regularized Pessimistic Value Iteration (R2PVI) algorithm that employs linear function approximation for robust policy learning in $d$-RRMDPs with $f$-divergence based regularization terms on transition kernels.
  arXiv  Detail & Related papers  (2024-11-27T18:57:03Z)
• Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs [63.47351876442425]
  We study episodic linear mixture MDPs with the unknown transition and adversarial rewards under full-information feedback. We propose a novel algorithm that combines the benefits of two popular methods: occupancy-measure-based and policy-based. Our algorithm enjoys an $widetildemathcalO(d sqrtH3 K + sqrtHK(H + barP_K$)$ dynamic regret, where $d$ is the feature dimension.
  arXiv  Detail & Related papers  (2024-11-05T13:55:52Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• Best of Both Worlds Policy Optimization [33.13041034490332]
  We show that by properly designing the regularizer, the exploration bonus and the learning rates, one can achieve a more favorable polylog$(T)$ regret when the losses are adversarial. This is the first time a gap-dependent polylog$(T)$ regret bound is shown for policy optimization.
  arXiv  Detail & Related papers  (2023-02-18T19:46:11Z)
• Gradient-Free Methods for Deterministic and Stochastic Nonsmooth Nonconvex Optimization [94.19177623349947]
  Non-smooth non optimization problems emerge in machine learning and business making. Two core challenges impede the development of efficient methods with finitetime convergence guarantee. Two-phase versions of GFM and SGFM are also proposed and proven to achieve improved large-deviation results.
  arXiv  Detail & Related papers  (2022-09-12T06:53:24Z)
• Faster Algorithm and Sharper Analysis for Constrained Markov Decision Process [56.55075925645864]
  The problem of constrained decision process (CMDP) is investigated, where an agent aims to maximize the expected accumulated discounted reward subject to multiple constraints. A new utilities-dual convex approach is proposed with novel integration of three ingredients: regularized policy, dual regularizer, and Nesterov's gradient descent dual. This is the first demonstration that nonconcave CMDP problems can attain the lower bound of $mathcal O (1/epsilon)$ for all complexity optimization subject to convex constraints.
  arXiv  Detail & Related papers  (2021-10-20T02:57:21Z)
• Optimistic Policy Optimization with Bandit Feedback [70.75568142146493]
  We propose an optimistic trust region policy optimization (TRPO) algorithm for which we establish $tilde O(sqrtS2 A H4 K)$ regret for previous rewards. To the best of our knowledge, the two results are the first sub-linear regret bounds obtained for policy optimization algorithms with unknown transitions and bandit feedback.
  arXiv  Detail & Related papers  (2020-02-19T15:41:18Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.