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

This work studies online episodic tabular Markov decision processes (MDPs) with known transitions and develops best-of-both-worlds algorithms that achieve refined data-dependent regret bounds in the adversarial regime and variance-dependent regret bounds in the stochastic regime. We quantify MDP complexity using a first-order quantity and several new data-dependent measures for the adversarial regime, including a second-order quantity and a path-length measure, as well as variance-based measures for the stochastic regime. To adapt to these measures, we develop algorithms based on global optimization and policy optimization, both built on optimistic follow-the-regularized-leader with log-barrier regularization. For global optimization, our algorithms achieve first-order, second-order, and path-length regret bounds in the adversarial regime, and in the stochastic regime, they achieve a variance-aware gap-independent bound and a variance-aware gap-dependent bound that is polylogarithmic in the number of episodes. For policy optimization, our algorithms achieve the same data- and variance-dependent adaptivity, up to a factor of the episode horizon, by exploiting a new optimistic $Q$-function estimator. Finally, we establish regret lower bounds in terms of data-dependent complexity measures for the adversarial regime and a variance measure for the stochastic regime, implying that the regret upper bounds achieved by the global-optimization approach are nearly optimal.

This paper investigates a hybrid reinforcement learning setting in tabular Markov Decision Processes (MDPs), where an agent aims to learn an optimal policy by combining online interactions with a target environment and offline data from a source environment. A central challenge is that offline data may be collected from outdated environments with shifted transition dynamics, making naive integration of historical data ineffective. To address this, we propose a unified algorithmic framework featuring two algorithms: MIN-UCB-VI for regret minimization and MAX-LCB-VI for best policy identification. Both algorithms leverage fine-grained bias information to more effectively exploit offline data under general transition shifts. We provide theoretical guarantees for our framework, including both instance-dependent and independent upper bounds on regret and sub-optimality gap. Furthermore, we establish matching lower bounds to demonstrate the optimality of our approach and validate our theoretical findings through extensive experiments.

Learning the optimal policy for Markov decision process problems (MDPs) from samples is a fundamental problem in online and data-driven decision-making. Function approximations are usually deployed to handle large or infinite state-action space. In our work, we consider the MDP problems with function approximation and we develop a new algorithm to solve it efficiently. Our algorithm is based on a linear programming (LP) reformulation and repeatedly resolves the identified reduced linear system as new transition samples arrive. After the optimal basis is identified, we show that, after $N$ resolving rounds, the expected averaged iterate achieves an instance-dependent $\widetilde O(C_{\mathrm{inst}}/N)$ objective shortfall and signed constraint residual. We separately account for the historical samples used for basis identification and the $d_2$ transition queries used in each resolving round, which yields the corresponding total transition-query complexity. We further complement our result with a \textit{robust} $O(1/\sqrt{N})$ bound that is independent of $Δ$. In comparison to the guarantees established in the previous literature, our instance dependent guarantee is tighter when the underlying instance is favorable, and the numerical experiments also reveal the wide applications and efficient empirical performances of our algorithms.