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.
A new method for CMDP solving without compromising safety constraints.
problem Solving CMDP problems while adhering to safety constraints.
method Decomposition into reconnaissance and planning MDPs.
result Achieves safe policies for any safety constraint set.
New method for optimistic planning in MDPs using regularization.
problem Optimistic planning in infinite-horizon discounted MDPs.
method Regularized dynamic programming for approximate value iteration.
result Achieves near-optimal statistical guarantees in learning policies.
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.
This paper presents a unifying framework for reinforcement learning and planning.
problem Sequential decision making in AI, formalized as MDP optimization.
method A unifying algorithmic framework (FRAP) for reinforcement learning and planning.
result Identifies common dimensions in MDP planning and learning algorithms.
This paper solves steady-state planning for multichain MDPs.
problem Specifying constraints on the steady-state behavior of an agent.
method Linear programming solution for multichain MDPs.
result Optimal solutions yield stationary policies with rigorous guarantees.
This work considers the sample and computational complexity of obtaining an ε ε ε -optimal policy in a discounted Markov Decision Process (MDP), given only access to a generative model. In this work, we study the effectiveness of the most natural plug-in approach to model-based planning: we build the maximum likelihood es…
State-of-the-art efficient model-based Reinforcement Learning (RL) algorithms typically act by iteratively solving empirical models, i.e., by performing \emph{full-planning} on Markov Decision Processes (MDPs) built by the gathered experience. In this paper, we focus on model-based RL in the finite-state finite-horizon…
Survey of integrating planning and learning in model-based reinforcement learning.
problem Sequential decision making in AI, formalized as MDP optimization.
method Systematic coverage of dynamics model learning and planning-learning integration.
result Broad conceptual overview of model-based reinforcement learning.
The explore{exploit dilemma is one of the central challenges in Reinforcement Learning (RL). Bayesian RL solves the dilemma by providing the agent with information in the form of a prior distribution over environments; however, full Bayesian planning is intractable. Planning with the mean MDP is a common myopic approxi…
New research shows exponential lower bounds for planning in MDPs with linearly-realizable optimal action-value functions.
problem Determining the minimum number of queries needed for sound planners in MDPs with linear function approximation.
method Analyzing fixed-horizon and discounted MDPs with a generative model, showing lower bounds on the number of queries required.
result Sound planners need at least exponential number of queries in both fixed-horizon and discounted settings.
TensorPlan shows an exponential lower bound for planning in MDPs with linearly realizable value functions.
problem Finding an exponential lower bound for planning in MDPs with linearly realizable value functions.
method TensorPlan and a few action lower bound approach.
result An exponentially large lower bound is shown for planning in MDPs with linearly realizable value functions.
Abstract MDPs enable strategic exploration and fast reward transfer in complex environments.
problem Challenging to learn accurate MDPs for high-dimensional states.
method Learn an abstract MDP over low-dimensional coarse states, using an abstraction function.
result Achieves superhuman performance on Pitfall! and higher reward with fewer samples.
New algorithm for RL with horizon-free reward-free exploration for linear MDPs.
problem Reward-free reinforcement learning with long planning horizons.
method Uncertainty-weighted value-targeted regression with exploration-driven pseudo-reward and moment estimator.
result Horizon-free sample complexity of O ( d 2 ε − 2 ) O(d^2\varepsilon^{-2}) O ( d 2 ε − 2 ) for finding an ε \varepsilon ε -optimal policy. We consider large-scale Markov decision processes (MDPs) with parameter uncertainty, under the robust MDP paradigm. Previous studies showed that robust MDPs, based on a minimax approach to handle uncertainty, can be solved using dynamic programming for small to medium sized problems. However, due to the "curse of dimen…
The paper studies risk-sensitive MDPs with recursive risk measures.
problem Risk-sensitive decision-making in MDPs with unbounded costs.
method Recursive application of static risk measures, Bellman equation derivation, existence of optimal policies.
result Existence of Markovian optimal policies for infinite planning horizons, contractive model for stationary optimal policy.
TensorPlan algorithm finds δ-optimal policies with poly ( H , d ) (H,d) ( H , d ) queries under linearly realizable state-value function.
problem Efficient planning in MDPs with linearly realizable state-value function.
method TensorPlan algorithm using poly ( ( d H / δ ) A ) ((dH/δ)^A) (( d H / δ ) A ) simulator queries. result First algorithm with polynomial query complexity using only linear-realizability of a single competing value function.
The study compares reinforcement learning models and finds model-based approaches superior for complex MDPs.
problem Complexity of optimal Q-functions and policies in MDPs exceeds dynamics, hindering model-free methods.
method Theoretical analysis and empirical testing of neural network expressivity for policies, Q-functions, and dynamics.
result Model-based planning yields better policies for complex MDPs, improving performance on MuJoCo tasks.
Reward tweaking optimizes behavior for long-term goals by adjusting the reward function.
problem Optimizing behavior for long-term goals in reinforcement learning with unstable long planning horizons.
method Reward tweaking learns a surrogate reward function that induces optimal behavior for the original task.
result Reward tweaking guides agents towards better long-term returns while planning for short horizons.
XLVINs improve deep reinforcement learning by combining self-supervised learning and neural algorithmic reasoning.
problem Limitations of Value Iteration Networks (VINs) in deep reinforcement learning.
method Combining contrastive self-supervised learning, graph representation learning, and neural algorithmic reasoning.
result XLVINs match VIN-like models on discrete, fixed MDPs and significantly outperform model-free baselines.
Paper proposes a method for learning and planning in time-varying environments.
problem Learning and planning in unknown, time-varying environments.
method Computes the maximally likely model of the environment using maximum likelihood estimation.
result Generalizes learning algorithms for time-invariant Markov decision processes to time-varying ones.
This work uses action equivariance to learn structured latent spaces for reinforcement learning.
problem Learning structured latent spaces for reinforcement learning.
method Introduced a contrastive loss function to enforce action equivariance on learned representations.
result Optimal policies in the abstract MDP can be successfully lifted to the original MDP.
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.
New algorithms accelerate value function convergence in MDPs.
problem Accelerating convergence of value functions in Markov Decision Processes (MDPs).
method Operator Splitting Value Iteration (OS-VI) and OS-Dyna.
result Achieves much faster convergence rate with accurate models.
This work tackles the problem of robust zero-shot planning in non-stationary stochastic environments. We study Markov Decision Processes (MDPs) evolving over time and consider Model-Based Reinforcement Learning algorithms in this setting. We make two hypotheses: 1) the environment evolves continuously with a bounded ev…
We introduce and analyse two algorithms for exploration-exploitation in discrete and continuous Markov Decision Processes (MDPs) based on exploration bonuses. SCAL + ^+ + is a variant of SCAL (Fruit et al., 2018) that performs efficient exploration-exploitation in any unknown weakly-communicating MDP for which an upper bo…
New RL approach tackles non-linear MDPs without linear assumptions.
problem Sample efficiency in RL for complex, nonlinear MDPs with continuous states.
method Introduces EPW condition to relax linear structure requirements; provides sample-efficient RL algorithm.
result EPW condition allows solving MDPs without linear assumptions, including Atari games.
New algorithm learns optimal policies in strategic MDPs with private types.
problem Optimal policy learning in strategic MDPs with private types and information asymmetry.
method PLAN algorithm using instrumental variable regression and pessimism principle.
result PLAN achieves near-optimal policy with 1 / K 1 / \sqrt{K} 1/ K optimality. New method approximates POMDPs with PB-MDPs, providing error bounds and practical algorithms.
problem Difficulty in solving POMDPs with continuous or hybrid state and observation spaces.
method Bounding particle filtering error and adapting MDP algorithms to POMDPs.
result General theory and practical algorithms for POMDPs with no direct dependence on state and observation space sizes.
Efficient RL for linear MDPs with unknown transitions.
problem Long planning horizons and unknown state transitions in linear mixture MDPs.
method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.
result Achieves optimal regret up to logarithmic factors.
This work clarifies the role of inference types in planning.
problem Lack of consistency in using inference types for planning.
method Variational framework and loopy belief propagation.
result All inference types correspond to different weights in variational problems.
New algorithm reduces reinforcement learning regret to sqrt(T) without strong dynamics assumptions.
problem Infinite-horizon average-reward reinforcement learning with linear MDPs.
method Approximate by discounted-reward MDPs and apply optimistic value iteration.
result Achieves O(sqrt(T)) regret with polynomial complexity.
TOMA generates abstract graphs for RL, reducing memory and computation costs.
problem High memory and computation costs in graph generation for RL.
method Topological Map Abstraction (TOMA) for generating abstract graphs.
result TOMA reduces memory and computation costs compared to existing methods.
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. 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.
FMDP-BF algorithm improves RL in factored MDPs with exponential regret reduction.
problem Efficient reinforcement learning in factored MDPs with constrained RL.
method FMDP-BF algorithm leveraging factorization structure of FMDPs.
result FMDP-BF's regret is exponentially smaller than optimal algorithms for non-factored MDPs.
Paper proposes a privacy-preserving RL algorithm for linear MDPs with theoretical guarantees.
problem Protecting users' private data in personalized services using RL.
method Local differential privacy (LDP) for RL with linear function approximation.
result Achieves a regret bound of $O(d^{5/4}H^{7/4}T^{3/4}\left(\log(1/δ)
ight)^{1/4}\sqrt{1/\varepsilon})$ for linear mixture MDPs.
New RL algorithm maximizes CVaR in low-rank MDPs with provable efficiency.
problem Maximizing CVaR in large state spaces with function approximation.
method Upper Confidence Bound (UCB) bonus-driven algorithm for low-rank MDPs.
result Achieves sample complexity of O(H^7 A^2 d^4 / τ^2 ε^2) for ε-optimal CVaR.
Study minimizes risk in MDPs with spectral measures.
problem Minimizing risk in MDPs with spectral measures.
method Splitting into inner and outer minimization problems; solving inner as MDP; proving existence for outer.
result Existence and solution methods for the outer minimization problem.
New RL approach uses resets to learn complex MDPs efficiently.
problem Learning complex MDPs with high-dimensional states and function approximation.
method Local simulator access and recursive value function search.
result Proven sample-efficient learning for MDPs with low coverability.
RandQL is a new model-free algorithm for MDPs with a novel learning rate randomization approach.
problem Minimizing regret in episodic MDPs with model-free methods.
method Randomized Q-learning with learning rate randomization.
result RandQL achieves optimal regret bounds in both tabular and metric state-action spaces.
New L 1 L_1 L 1 -Coverage objective simplifies exploration in reinforcement learning.
problem Challenges in exploration for high-dimensional domains.
method Introduces L 1 L_1 L 1 -Coverage objective to enable efficient exploration and planning. result First computationally efficient algorithms for online reinforcement learning with low coverability.
New RL algorithm achieves nearly optimal performance for linear MDPs.
problem Optimal reinforcement learning for episodic linear MDPs.
method Weighted linear regression with variance estimator and rare-switching policy.
result Achieves nearly minimax optimal regret i l d e O ( d H 3 K ) ilde O(d\sqrt{H^3K}) i l d e O ( d H 3 K ) . Enhances RL with function approximation, improving regret bounds.
problem Improving exploration in reinforcement learning with function approximation.
method Prior-dependent Bayesian regret bound for PSRL with linear mixture MDPs, using value-targeted model learning and variance reduction.
result Established an upper bound of O ( d H 3 T log T ) {\mathcal{O}}(d\sqrt{H^3 T \log T}) O ( d H 3 T log T ) for PSRL. Efficiently computes optimal policies for Entropic Risk Measures.
problem Optimizing risk-sensitive metrics in MDPs is computationally expensive.
method Uses Entropic Risk Measures and novel structural analysis for efficient computation.
result Achieves strong performance in various decision-making scenarios.
Optimistic algorithm reduces regret in non-stationary linear MDPs.
problem Efficient learning in non-stationary linear MDPs with evolving reward and transition.
method OPT-WLSVI, an optimistic model-free algorithm using exponential weights.
result Achieves a regret bound of O ~ ( d 5 / 4 H 2 Δ 1 / 4 K 3 / 4 ) \widetilde{\mathcal{O}}(d^{5/4}H^2 Δ^{1/4} K^{3/4}) O ( d 5/4 H 2 Δ 1/4 K 3/4 ) . A new method for multi-agent planning on graphs outperforms existing approaches.
problem Planning coordination among multiple interacting agents on a graph.
method Variational perturbation theory applied to inference in large networks.
result Our method outperforms state-of-the-art methods in non-local cost function scenarios.
Safe exploration in RF-RL doesn't increase sample complexity.
problem Achieving optimal policies with safety constraints in reward-free RL.
method Proposed SWEET framework for tabular and low-rank MDP settings, leveraging truncated value functions.
result Sample complexities match or outperform constraint-free counterparts, proving safety constraints have little impact.