Any reinforcement learning algorithm that applies to all Markov decision processes (MDPs) will suffer regret on some MDP, where is the elapsed time and and are the cardinalities of the state and action spaces. This implies time to guarantee a near-optimal policy. In many settings…
On-device research index
arXiv research
A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
168,695 papers · 148 categories
Trend · papers per month
48 results for “factored MDPs”
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.
Improved exploration in factored average-reward MDPs reduces regret.
problem Minimizing regret in unknown Factored Markov Decision Processes (FMDPs).
method DBN-UCRL strategy, inspired by UCRL2, uses Bernstein-type confidence sets for individual elements of the transition function.
result Achieves a regret bound with a leading term strictly improving over existing bounds.
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.
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 for structured MDPs.
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.
Paper proposes an efficient RL algorithm for discounted MDPs using feature mapping.
problem Efficient reinforcement learning for large state and action spaces.
method Uses feature mapping to represent states and actions in a low-dimensional space, proposing a novel algorithm with polynomial regret bound.
result Achieves a regret bound, near-optimal up to a factor.
Study minimax optimal RL in factored MDPs with bonus exploration.
problem Optimal reinforcement learning in episodic factored MDPs.
method Proposes two model-based algorithms with bonus exploration for minimax optimal regret.
result Achieves minimax optimal regret guarantees for rich factored structures.
New formalism for decision making combines causal structures with MDPs, improving reinforcement learning performance.
problem Sequential decision making with causal knowledge to improve performance.
method Causal Markov Decision Processes (C-MDPs) and C-UCBVI algorithm exploiting causal structure.
result C-UCBVI achieves an regret bound, independent of actions.
We study reinforcement learning in non-episodic factored Markov decision processes (FMDPs). We propose two near-optimal and oracle-efficient algorithms for FMDPs. Assuming oracle access to an FMDP planner, they enjoy a Bayesian and a frequentist regret bound respectively, both of which reduce to the near-optimal bound …
New method achieves nearly horizon-free offline reinforcement learning for tabular and linear MDPs.
problem Achieving efficient reinforcement learning without knowing the horizon.
method Simple recursion-based method to bound total variance in offline scenarios.
result Nearly horizon-free sample complexity bounds for offline policy evaluation and optimization.
There is broad interest in creating RL agents that can solve many (related) tasks and adapt to new tasks and environments after initial training. Model-based RL leverages learned surrogate models that describe dynamics and rewards of individual tasks, such that planning in a good surrogate can lead to good control of t…
Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcs.LG
This paper improves reinforcement learning efficiency for large-scale MDPs.
problem High sample complexity in tabular RL settings with large state and action spaces.
method Model-based approach and Q-learning with linearly parameterized features.
result Provably efficient learning with sample complexity bounds.
We present an algorithm based on the \emph{Optimism in the Face of Uncertainty} (OFU) principle which is able to learn Reinforcement Learning (RL) modeled by Markov decision process (MDP) with finite state-action space efficiently. By evaluating the state-pair difference of the optimal bias function , the propos…
Policy analysts wish to visualize a range of policies for large simulator-defined Markov Decision Processes (MDPs). One visualization approach is to invoke the simulator to generate on-policy trajectories and then visualize those trajectories. When the simulator is expensive, this is not practical, and some method is r…
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.
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))
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 .
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.
New algorithm learns FMDP structure while minimizing regret.
problem Regret minimization in FMDPs with unknown structure.
method Optimism in face of uncertainty principle combined with statistical structure learning.
result First algorithm to learn FMDP structure while minimizing regret.
A Model-free Learning Algorithm for Infinite-horizon Average-reward MDPs with Near-optimal Regretcs.LG
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 regret bound for general weakly communicating MDPs.
New RL algorithm for linear MDPs with nearly optimal regret.
problem Optimizing reinforcement learning for linear mixture Markov decision processes.
method Proposed a new Bernstein-type concentration inequality for self-normalized martingales and a computationally efficient algorithm UCRL-VTR+.
result UCRL-VTR+ achieves nearly minimax optimal regret of .
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.
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 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.
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.
We propose a new complexity measure for Markov decision processes (MDPs), the maximum expected hitting cost (MEHC). This measure tightens the closely related notion of diameter [JOA10] by accounting for the reward structure. We show that this parameter replaces diameter in the upper bound on the optimal value span of a…
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 with matching lower bound.
Lower bounds for PI on multi-action MDPs are established, showing complexity grows with action count.
problem Establishing the minimum number of iterations for PI to converge on MDPs with multiple actions.
method Developed lower bounds for a specific PI variant on multi-action MDPs, scaling with action count.
result A particular PI variant can take iterations to terminate, scaling with action count.
In this paper, we settle the sampling complexity of solving discounted two-player turn-based zero-sum stochastic games up to polylogarithmic factors. Given a stochastic game with discount factor we provide an algorithm that computes an -optimal strategy with high-probability given $\tilde{O}((1 - γ)^{-3}…
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.
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.
We consider deterministic Markov decision processes (MDPs) and apply max-plus algebra tools to approximate the value iteration algorithm by a smaller-dimensional iteration based on a representation on dictionaries of value functions. The setup naturally leads to novel theoretical results which are simply formulated due…
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 .
result Achieved optimal dependence in linear MDPs for reward-free RL, matching the reward-aware RL setting.
We consider reinforcement learning in parameterized Markov Decision Processes (MDPs), where the parameterization may induce correlation across transition probabilities or rewards. Consequently, observing a particular state transition might yield useful information about other, unobserved, parts of the MDP. We present a…
UCB-Advantage learns MDPs with regret.
problem Model-free reinforcement learning in finite-horizon MDPs.
method Reference-Advantage decomposition for low regret.
result Achieves regret, matching best known bounds.
A fundamental question in reinforcement learning is whether model-free algorithms are sample efficient. Recently, Jin et al. \cite{jin2018q} proposed a Q-learning algorithm with UCB exploration policy, and proved it has nearly optimal regret bound for finite-horizon episodic MDP. In this paper, we adapt Q-learning with…
CPPO learns policies from partial offline data in MDPs with structural assumptions.
problem Offline Reinforcement Learning with partial coverage assumption.
method Constrained Pessimistic Policy Optimization (CPPO) using a function class and model class constraint.
result CPPO achieves PAC guarantee with partial coverage, learning competitive policies.
Improved Regret Analysis for Variance-Adaptive Linear Bandits and Horizon-Free Linear Mixture MDPsstat.ML
Significant improvements in regret analysis for adaptive online learning problems.
problem Exploiting low variance in online learning problems without known variances.
method Novel peeling-based regret analysis leveraging elliptical potential `count` lemma.
result Significant improvements in regret bounds for linear bandits and linear mixture MDPs.
Algorithm POLO learns low-rank MDPs with adversarial changes in full-info feedback.
problem Learning low-rank MDPs with adversarial changes and unknown transition probabilities.
method Policy optimization-based algorithm POLO with regret guarantee.
result POLO achieves sublinear regret guarantee with no dependence on state space size.
A new method for solving complex sequential decision-making problems by decomposing them into multiple levels.
problem Sequential decision-making with natural multi-level structure.
method Multi-level meta-reinforcement learning with skill-based curriculum.
result Efficiently reduces stochasticity and policy search space, leading to fewer iterations and computations.
Leveraging an equivalence property in the state-space of a Markov Decision Process (MDP) has been investigated in several studies. This paper studies equivalence structure in the reinforcement learning (RL) setup, where transition distributions are no longer assumed to be known. We present a notion of similarity betwee…
Improved model-free RL algorithm with reduced sample complexity.
problem Learning optimal policies in discounted MDPs efficiently.
method Proposes new algorithms with improved sample complexity bounds.
result Achieves better sample complexity than existing methods.
A new framework reduces RL sample complexity for complex MDPs.
problem Handling large state and action spaces in reinforcement learning.
method Unified model-based and model-free RL framework with ABC class, novel estimation function, and functional eluder dimension.
result OPERA algorithm achieves sample-efficient regret bounds for various MDP models.
New algorithm reduces offline RL data requirements significantly.
problem Optimizing policies using only historical data in reinforcement learning.
method Off-Policy Double Variance Reduction (OPDVR) algorithm.
result OPDVR achieves optimal sample complexity with episodes.
N-discount optimality was introduced as a hierarchical form of policy- and value-function optimality, with Blackwell optimality lying at the top level of the hierarchy Veinott (1969); Blackwell (1962). We formalize notions of myopic discount factors, value functions and policies in terms of Blackwell optimality in MDPs…
This paper is concerned with offline reinforcement learning (RL), which learns using pre-collected data without further exploration. Effective offline RL would be able to accommodate distribution shift and limited data coverage. However, prior algorithms or analyses either suffer from suboptimal sample complexities or …
We integrate information-theoretic concepts into the design and analysis of optimistic algorithms and Thompson sampling. By making a connection between information-theoretic quantities and confidence bounds, we obtain results that relate the per-period performance of the agent with its information gain about the enviro…