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…
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.
169,181 papers · 148 categories
Trend · papers per month
48 results for “Large Scale MDP”
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 algorithm handles MDPs with unknown, changing rewards efficiently.
problem Handling MDPs with unknown, changing rewards in large state spaces.
method Developed an algorithm with regret bound and a modified algorithm with polynomial complexity.
result Achieved state-of-the-art regret bounds for large scale MDPs with changing rewards.
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.
Proposes a new DQN framework using variational inference.
problem Efficient exploration and large-scale MDPs.
method Variational inference for value function parameters.
result Achieves efficient exploration on large-scale MDPs.
Deep RL solves combinatorial selection problems with large item spaces.
problem Solving MDPs with large state and action spaces, especially for combinatorial selection.
method Convert S-MDP to IS-MDP, use weight-shared Q-networks to manage state space explosion.
result Our approach effectively handles large item spaces and scales to diverse environments.
New algorithms approximate state similarity in large MDPs.
problem Computing exact bisimulation metrics in large MDPs is expensive and impractical.
method Developed a new metric tied to behavior policy, and two algorithms for approximating it.
result Presented algorithms that can approximate bisimulation metrics in large, deterministic MDPs.
Deep reinforcement learning (deep RL) has been successful in learning sophisticated behaviors automatically; however, the learning process requires a huge number of trials. In contrast, animals can learn new tasks in just a few trials, benefiting from their prior knowledge about the world. This paper seeks to bridge th…
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.
Solves action selection for large spaces in RL, achieving near-optimal performance.
problem Selecting a small, representative subset of actions from a large, shared action space.
method Extends meta-bandit approach to MDPs, using a relaxed sub-Gaussian process model.
result Achieves performance comparable to full action space, with theoretical guarantees.
Two new algorithms improve model-free RL for infinite-horizon MDPs.
problem Learning in infinite-horizon average-reward MDPs.
method Two model-free algorithms for infinite-horizon average-reward MDPs.
result Improved regret bounds for model-free RL in MDPs.
SCAL algorithm reduces exploration-exploitation in unknown MDPs with bias span constraints.
problem Efficient exploration-exploitation in unknown weakly-communicating MDPs with bias span constraints.
method Introduces SCAL, an algorithm that proves a regret bound of O(c√(ΓSAT)) for unknown MDPs with known bias span.
result SCAL significantly outperforms existing algorithms like UCRL and PSRL in MDPs with large diameter and small bias span.
Proves error bounds for state representation in RL using graph spectral features.
problem Addressing the curse of dimensionality in RL with unknown transition graphs.
method Proves upper bounds on approximation error of linear value function approximation using learned spectral features of the state-graph.
result Error bounds scale with algebraic connectivity and eigenvector estimation error.
MQGrad uses reinforcement learning to dynamically adjust gradient quantization bits.
problem Reduction of communication overhead in large-scale machine learning model training.
method Reinforcement learning applied to gradient quantization in parameter server.
result MQGrad accelerates deep neural network learning while maintaining prediction accuracy.
New RL method reduces sample complexity for large state-action spaces.
problem Handling large state-action spaces in RL with general Q-functions.
method Nonparametric Q-learning using kernel ridge regression.
result Sample complexity is order optimal with respect to ε and kernel complexity.
Bayesian regularization improves policy performance in noisy MDPs.
problem Suboptimal policies from estimated model parameters.
method Bayesian regularization of MDP objective function with prior information.
result Regularized policies show better robustness against model noise.
The use of Reinforcement Learning in real-world scenarios is strongly limited by issues of scale. Most RL learning algorithms are unable to deal with problems composed of hundreds or sometimes even dozens of possible actions, and therefore cannot be applied to many real-world problems. We consider the RL problem in the…
Algorithm reduces exploration in structured RL problems.
problem Minimize exploration in reinforcement learning with known structure.
method Directed Exploration Learning (DEL) for Lipschitz MDPs.
result Regret lower bounds not scaling with state and action space sizes.
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.
Unified framework for maximum entropy RL using Tsallis entropy.
problem Generalizing maximum entropy reinforcement learning with various entropies.
method Tsallis MDPs with Tsallis entropy maximization, controlling entropic index.
result Different entropic indices lead to different optimal policies and exploration tendencies.
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…
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…
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 model-free algorithms learn representations for low-rank MDPs efficiently.
problem Learning representations in reinforcement learning for low-rank MDPs.
method Developed minimax representation learning objective and interleaved with reward-free exploration.
result Proven sample efficiency and scalability to complex environments.
Efficient exploration in complex environments remains a major challenge for reinforcement learning. We propose bootstrapped DQN, a simple algorithm that explores in a computationally and statistically efficient manner through use of randomized value functions. Unlike dithering strategies such as epsilon-greedy explorat…
Optimizes Q-learning for MDPs with linear features, achieving sample efficiency.
problem Finding optimal policies in large-scale MDPs with limited samples.
method Parametric Q-learning with linearly additive features, exploiting monotonicity and noise structure.
result Proves sample optimality with samples for -optimality.
New algorithm tackles non-stationary reinforcement learning with general function approximation.
problem Understanding non-stationary MDPs with function approximation.
method Dynamic Bellman Eluder (DBE) dimension for complexity, sliding window mechanism, confidence set design.
result Upper bound on dynamic regret for proposed SW-OPEA algorithm.
We study reinforcement learning under model misspecification, where we do not have access to the true environment but only to a reasonably close approximation to it. We address this problem by extending the framework of robust MDPs to the model-free Reinforcement Learning setting, where we do not have access to the mod…
Efficient Learning for Entropy-Regularized Markov Decision Processes via Multilevel Monte Carlocs.LG
New algorithms reduce complexity for learning in MDPs with entropy regularization.
problem Efficient learning for MDPs with large or continuous state and action spaces.
method Multilevel Monte Carlo (MLMC) algorithms integrating fixed-point iteration and stochastic approximation of the Bellman operator.
result MLMC with unbiased approximation of the Bellman operator achieves polynomial sample complexity.
ARL uses MCTS to explore rewards efficiently, outperforming standard RL methods.
problem Challenging exploration in ARL due to limited reward feedback.
method ARL algorithm using MCTS, based on Bayes-Adaptive MDPs.
result Near-optimal performance on small problems, superior to Q-learners on larger ones.
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.
Study shows high-dimensional sparse RL hardness and Lasso Q-iteration's nearly dimension-free regret.
problem Hardness of online sparse reinforcement learning in high-dimensional MDPs.
method Lower bound construction and Lasso fitted Q-iteration analysis.
result Lasso Q-iteration achieves nearly dimension-free regret of with oracle access to a good exploratory policy.
New method removes oracle and reduces memory usage for robust MDPs.
problem Applying robust MDPs in practice due to model estimation and oracle requirements.
method Transformed robust MDPs into an alternative form allowing stochastic gradient methods and model-free approach.
result Sample-efficient algorithm with lower storage requirement and no oracle.
NNQL learns Q-function from single sample path in continuous state space MDPs.
problem Learning optimal Q-function in MDPs with unknown transition kernel and continuous state space.
method Nearest Neighbor Q-Learning (NNQL) using nearest neighbor regression.
result NNQL achieves -accurate Q-function estimation with samples.
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.
Policy gradient methods achieve linear convergence in simple MDPs.
problem Analyzing convergence rates of policy gradient methods in finite MDPs.
method Connections with policy iteration to show linear convergence with large step-sizes.
result Policy gradient methods succeed with large step-sizes and achieve linear rate of convergence.
New algorithm learns optimal policies efficiently with minimal memory.
problem Optimal policy learning in large-scale MDPs.
method Bilinear π learning using state and action features.
result Sample-efficient, solving optimal policy with linear sample complexity.
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.
Study preference-based reinforcement learning in episodic kernel MDPs.
problem Learning from episodic human preferences in reinforcement learning.
method Developed preference-based value estimation and confidence sets for kernel-based MDPs.
result Proved high-probability regret bounds that converge to optimal policy value.
Stochastic domains often involve risk-averse decision makers. While recent work has focused on how to model risk in Markov decision processes using risk measures, it has not addressed the problem of solving large risk-averse formulations. In this paper, we propose and analyze a new method for solving large risk-averse …
Adaptive Trust Region Policy Optimization: Global Convergence and Faster Rates for Regularized MDPscs.LG
TRPO adapts trust region methods for faster RL convergence.
problem Improving RL convergence rates in regularized MDPs.
method Adaptive scaling in TRPO for faster convergence rates.
result First RL result showing faster rates with regularization.
HL algorithms improve resource allocation in cloud environments.
problem Sequential decision-making under uncertainty with exogenous variables.
method HL algorithms leverage exogenous variable samples to infer counterfactual consequences.
result HL algorithms outperform classic methods and reinforcement learning in resource allocation.
KeRNS tackles non-stationary reinforcement learning in metric spaces.
problem Non-stationary reinforcement learning in metric spaces.
method KeRNS uses time-dependent kernels to model non-stationary Markov Decision Processes (MDPs).
result KeRNS achieves a regret bound that scales with the covering dimension and total variation of the MDP.
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 in infinite-horizon average-reward MDPs.
Improved regret bound for reinforcement learning in MDPs with variance consideration.
problem Minimax lower bound for reinforcement learning in unknown MDPs.
method Novel analysis of KL-UCRL algorithm with variance-aware regret bound.
result Regret bound scaling as for ergodic MDPs.
Many problems in sequential decision making and stochastic control often have natural multiscale structure: sub-tasks are assembled together to accomplish complex goals. Systematically inferring and leveraging hierarchical structure, particularly beyond a single level of abstraction, has remained a longstanding challen…
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.