Adaptive reduction scheme approximates optimal policy in regularized MDPs.
problem Finding near optimal policy in regularized MDPs with biased solutions.
method Adaptive reduction of regularization parameter λ to approximate optimal policy.
result Iteration complexity reduced for obtaining ε-optimal policy.
In this paper, a sparse Markov decision process (MDP) with novel causal sparse Tsallis entropy regularization is proposed.The proposed policy regularization induces a sparse and multi-modal optimal policy distribution of a sparse MDP. The full mathematical analysis of the proposed sparse MDP is provided.We first analyz…
Optimizes learning policies in average-reward MDPs with improved sample complexity.
problem Learning optimal policies in average-reward MDPs with limited samples.
method Reduces to discounted MDPs and uses improved bounds for variance parameters.
result Establishes minimax optimal sample complexity bound of O(SA(H/ε^2))
Optimizes learning policies in MDPs with weakly communicating structure.
problem Learning optimal policies in weakly communicating MDPs with generative model.
method Span-based approach, reducing to discounted MDPs for analysis.
result First minimax optimal sample complexity bound for weakly communicating MDPs.
We solve POMDPs by approximating them as finite-state MDPs.
problem Computational challenges in learning optimal policies for POMDPs.
method Transform POMDP into a Superstate MDP, apply TD-learning and policy optimization.
result Finite-time bounds on TD-learning error for non-Markovian dynamics.
Efficiently plans large MDPs with weak function approximations.
problem Planning in large MDPs with limited function approximation capabilities.
method Uses linear value function approximation with weak requirements and a generative oracle.
result Produces almost-optimal actions for any state with polynomial computation time.
New method for estimating and optimizing MDPs without stationarity.
problem Challenges in offline contextual MDP estimation without stationarity.
method Introduces a new adaptive estimation and cost optimization approach for contextual MDPs.
result First robust, theoretically backed method for offline contextual MDP estimation.
Paper optimizes learning MDPs with adversarial rewards using linear models.
problem Learning MDPs with adversarial rewards and changing reward functions.
method Proposes POWERS, an optimistic policy optimization algorithm.
result Achieves nearly optimal regret bound of O ( d H T ) O(dH\sqrt{T}) O ( d H T ) . UCBVI-γ algorithm minimizes regret in discounted MDPs.
problem Minimizing regret in discounted MDPs.
method Optimism in the face of uncertainty principle and Bernstein-type bonus.
result UCBVI-γ achieves nearly minimax optimal regret.
A new parallel algorithm for learning optimal policies in MDPs with low communication costs.
problem Learning optimal policies for infinite-horizon MDPs.
method Primal-Dual Stochastic Mirror Descent for convex programming problems with inexact constraints.
result First parallel algorithm for average-reward MDPs with generative model and low communication costs.
This work extends ME-RL using diffusion models to sample optimal policies.
problem Sampling from the optimal policy trajectory distribution in ME-RL.
method Introducing Diffusion-Augmented Markov Decision Processes (DA-MDPs) to minimize reverse KL divergence.
result DA-MDPs enable seamless integration into various ME-RL methods and outperform baselines.
Improved regret bound for MNL MDPs with variance-aware approach.
problem Optimal reinforcement learning for MNL MDPs with structured variance.
method Introducing a problem-dependent constant measuring average variance, proposing an algorithm with improved regret bound.
result Minimax optimal regret bound of O ( d H 2 σ ˉ T T ) O(dH^2\barσ_T\sqrt{T}) O ( d H 2 σ ˉ T T ) for structured MDPs. New algorithm for offline RL with linear approx in MDPs and MGs, nearly optimal.
problem Offline RL with linear function approximation in MDPs and MGs.
method Pessimism-based algorithm with uncertainty decomposition via reference function.
result Nearly minimax optimal performance in offline RL for MDPs and MGs.
Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer Ω ( S A T ) Ω(\sqrt{SAT}) Ω ( S A T ) regret on some MDP, where T T T is the elapsed time and S S S and A A A are the cardinalities of the state and action spaces. This implies T = Ω ( S A ) T = Ω(SA) T = Ω ( S A ) time to guarantee a near-optimal policy. In many settings…
Paper establishes first instance-dependent lower bound for PAC reinforcement learning.
problem Identifying near-optimal policies in tabular MDPs with minimal samples.
method Proposes instance-dependent lower bound for sample complexity.
result Lower bound closely matches PEDEL algorithm's sample complexity.
Paper bounds PAC RL sample complexity in deterministic MDPs.
problem Identify ε-optimal policy with high probability.
method Proposes nearly matching upper and lower bounds on sample complexity, introduces deterministic return gap, uses graph-theoretical concepts and maximum-coverage exploration.
result First nearly matching upper and lower bounds on sample complexity for PAC RL in deterministic MDPs.
New method optimizes ambiguity sets for robust MDPs, improving policy robustness.
problem Sensitivity of optimal policies to model misspecification in MDPs.
method Proposes a new approach to optimize the shape of ambiguity sets, departing from norm-bounded uniform and symmetric sets.
result Empirical results show practical promise of weighted near-optimal ambiguity sets.
RL approach for target tracking with unknown dynamics and sensor control.
problem Tracking an unknown target with sensor control.
method Track-MDP formulation for RL, compared with POMDP.
result Optimal RL policy tracks all target paths with certainty.
Proposes a Riemannian optimization for policy improvement in MDPs.
problem Optimizing policy functions in Markov decision processes (MDPs).
method Riemannian proximal optimization algorithm with Gaussian mixture model (GMM).
result Guaranteed convergence and efficacy demonstrated in preliminary experiments.
We decode latent states in Block MDPs and learn near-optimal policies.
problem Model estimation and reward-free learning in Block MDPs.
method Information-theoretical lower bound and efficient model estimation algorithm.
result Our algorithm approaches the information-theoretical limit for latent state decoding and converges to optimal policies.
New RL algorithm tackles online robust MDPs with uncertainty.
problem Developing robust reinforcement learning models for real-world environments.
method Proposes a robust optimistic policy optimization algorithm for online robust MDPs.
result Establishes the first regret bound for online robust MDPs.
Paper identifies reductive MDPs, solving them in polynomial time.
problem Computational hardness of general MDPs and tractability of finite-horizon MDPs.
method Defines reductivity, a new class of SSPs, and develops a polynomial-time solution.
result Optimal policies can be found in polynomial time for reductive SSPs and MDPs.
We consider a new form of reinforcement learning (RL) that is based on opportunities to directly learn the optimal control policy and a general Markov decision process (MDP) framework devised to support these opportunities. Derivations of general classes of our control-based RL methods are presented, together with form…
New method tackles MDPs by learning normalized representations efficiently.
problem Curse of dimensionality in MDPs.
method Contrastive representation learning for linear MDPs.
result First practical method with strong theoretical guarantees and empirical performance.
UCRL2-VTR achieves nearly optimal regret for learning MDPs with linear function approximation.
problem Learning infinite-horizon average-reward MDPs with linear function approximation.
method UCRL2-VTR algorithm with Bernstein-type bonus.
result Achieves a regret of i l d e O ( d D T ) ilde{O}(d\sqrt{DT}) i l d e O ( d D T ) with matching lower bound. The paper improves regret lower bounds for communicating MDPs.
problem Regret lower bounds for communicating MDPs.
method Lower bound proof and optimization problem formulation.
result Regret lower bound becomes significantly more complex in communicating MDPs.
Improved exploration in adversarial MDPs via dilated bonuses.
problem Global exploration in adversarial MDPs with local-search policies.
method Dilated bonuses to facilitate global exploration.
result Improved regret bounds in various MDP settings.
We consider the Markov Decision Process (MDP) of selecting a subset of items at each step, termed the Select-MDP (S-MDP). The large state and action spaces of S-MDPs make them intractable to solve with typical reinforcement learning (RL) algorithms especially when the number of items is huge. In this paper, we present …
Reward-free RL in linear MDPs is as hard as reward-aware RL.
problem Reward-free RL in linear MDPs without access to the reward function during exploration.
method Developed a computationally efficient algorithm with sample complexity O ~ ( d 2 H 5 / ε 2 ) \widetilde{\mathcal{O}}(d^2 H^5/ε^2) O ( d 2 H 5 / ε 2 ) . result Achieved optimal d d d dependence in linear MDPs for reward-free RL, matching the reward-aware RL setting. A new model-free algorithm achieves near-optimal regret for infinite-horizon MDPs.
problem Model-free reinforcement learning for infinite-horizon average-reward MDPs.
method Exploration Enhanced Q-learning (EE-QL) for weakly communicating MDPs.
result Achieves O ( T ) O(\sqrt{T}) O ( T ) regret bound for general weakly communicating MDPs. A Markov Decision Process (MDP) is a popular model for reinforcement learning. However, its commonly used assumption of stationary dynamics and rewards is too stringent and fails to hold in adversarial, nonstationary, or multi-agent problems. We study an episodic setting where the parameters of an MDP can differ across…
New algorithm reduces sample complexity for planning in MDPs.
problem Planning in MDPs with unknown transitions.
method MDP-GapE, a trajectory-based MCTS algorithm.
result Proves upper bound on sample complexity in terms of sub-optimality gaps.
New bounds for learning near-optimal policies in CMDPs with constraints.
problem Optimizing policies in CMDPs with constraints.
method Model-based algorithm addressing relaxed and strict feasibility.
result Near-optimal sample complexity bounds for CMDPs.
MetaCURL tackles non-stationary MDPs with optimal dynamic regret.
problem Online learning in non-stationary Markov decision processes.
method MetaCURL uses a meta-algorithm with multiple black-box algorithms and a sleeping expert framework.
result Achieves optimal dynamic regret without prior knowledge of MDP changes.
Study on policy testing in MDPs with lower bounds and new algorithm.
problem Deciding if policy value exceeds a threshold with limited samples.
method Derived lower bound, proposed new algorithm, reformulated problem, used policy optimization in reversed MDP.
result New algorithm outperforms existing methods in policy testing.
MOReL learns offline RL policies using pessimistic MDPs.
problem Offline RL's data efficiency and velocity.
method Two-step process: learn P-MDP and near-optimal policy in it.
result MOReL is minimax optimal and matches state-of-the-art results.
New method for RL tasks transfer using Lipschitz continuity.
problem Knowledge transfer in RL tasks over time.
method Established Lipschitz continuity between MDPs and applied it to RL.
result Improved convergence rate and no negative transfer with high probability.
Unified framework for solving MDPs with stochastic mirror descent.
problem Approximately solving infinite-horizon Markov decision processes (MDPs).
method Primal-dual stochastic mirror descent for MDPs with a unified framework.
result Computes ε-optimal policies with expected samples for both average-reward and discounted MDPs.
Optimizes policies for reinforcement learning with limited data.
problem Computing reliable policies with high confidence in reinforcement learning problems.
method Robust MDPs (RMDPs) with weighted L1 and L∞ norms to minimize ambiguity set spans.
result Optimized ambiguity sets improve policy performance significantly.
Optimistic PPO variant solves linear MDPs with improved regret bound.
problem Understanding theoretical limits of PPO in linear MDPs.
method Proposes an optimistic variant of PPO for episodic adversarial linear MDPs with full-information feedback.
result Establishes a i l d e O ( d 3 / 4 H 2 K 3 / 4 ) ilde{\mathcal{O}}(d^{3/4}H^2K^{3/4}) i l d e O ( d 3/4 H 2 K 3/4 ) regret bound. The paper establishes a nearly-sharp statistical threshold for efficient learning in Latent MDPs with separated components.
problem Learning Latent Markov Decision Processes (LMDPs) with separated components.
method The paper considers various notions of separation and establishes a nearly-sharp statistical threshold for efficient learning. It also presents a quasi-polynomial algorithm with time complexity scaling in terms of the statistical threshold under a weaker assumption of separability under the optimal policy, and a near-matching time complexity lower bound under the exponential time hypothesis.
result Establishes a nearly-sharp statistical threshold for efficient learning in Latent MDPs with separated components.
We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound c c c on the span of the optimal bias function is known. For an MDP with S S S states, A A A actions and Γ ≤ S Γ\leq S Γ ≤ S possible next states, we prove a …
Actor-Critic method achieves optimal regret for unichain MDPs.
problem Scalable regret analysis for infinite-horizon average-reward MDPs.
method NAC-B, a Natural Actor-Critic with batching.
result Order-optimal regret of i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) in infinite-horizon average-reward MDPs. Logarithmic regret achieved in RL with linear function approximation.
problem Achieving logarithmic regret in reinforcement learning with linear function approximation.
method LSVI-UCB for linear MDP assumption, UCRL-VTR for linear mixture MDP assumption.
result Logarithmic regret bounds established for RL with linear function approximation.
The paper tackles reinforcement learning with exogenous variables and rewards.
problem Exogenous state variables and rewards slow reinforcement learning by introducing uncontrolled variation.
method Formalizes exogenous state variables and rewards, decomposes MDP into exogenous and endogenous components, and introduces algorithms to discover these components.
result Optimal policies for the endogenous MDP are also optimal for the original MDP, but the endogenous MDP is easier to solve due to reduced variance.
PROPO tackles non-stationary MDPs with efficient policy optimization.
problem Non-stationary MDPs with varying reward and transition kernels.
method PROPO, a periodic restarted optimistic policy optimization algorithm with sliding-window-based policy evaluation and improvement.
result PROPO achieves near-optimal performance in non-stationary MDPs.
DeepAveragers solves offline RL by solving derived MDPs from static data.
problem Offline reinforcement learning with limited data.
method Solves derived non-parametric MDPs (DAC-MDPs) using deep representations and costs for under-represented parts.
result The approach can lower-bound performance and scale to complex offline RL problems.
Paper improves sample complexity for reward-free RL in low-rank MDPs.
problem Reward-free RL in low-rank MDPs with unknown representation and weights.
method Proposes a novel model-based algorithm RAFFLE with improved sample complexity.
result RAFFLE achieves ε ε ε -optimal policy and accurate system identification with significantly fewer samples.