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…
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 “Sparse MDP”
We propose and study a general framework for regularized Markov decision processes (MDPs) where the goal is to find an optimal policy that maximizes the expected discounted total reward plus a policy regularization term. The extant entropy-regularized MDPs can be cast into our framework. Moreover, under our framework, …
New algorithm learns sparse linear MDPs with polynomial interactions, improving sample complexity.
problem Learning optimal policies in sparse linear MDPs with limited interactions and unknown features.
method Developed a polynomial-time algorithm using feature selection and emulator for sparse linear MDPs.
result First polynomial-time algorithm for learning near-optimal policies in k-sparse linear MDPs.
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.
Markov Decision Processes (MDPs) are a mathematical framework for modeling sequential decision making under uncertainty. The classical approaches for solving MDPs are well known and have been widely studied, some of which rely on approximation techniques to solve MDPs with large state space and/or action space. However…
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.
We propose an algorithm for deterministic continuous Markov Decision Processes with sparse rewards that computes the optimal policy exactly with no dependency on the size of the state space. The algorithm has time complexity of and memory complexity of , where is the…
VOL optimizes RL with sparse rewards using weighted bounds.
problem Sparse rewards and non-linear function approximation in RL.
method VOL combines -learning with weighted bounds for optimal regret.
result Achieves asymptotically optimal regret for linear function approximation.
UCB-TQL learns from multiple tasks with shared dynamics and adapts to task-specific variations.
problem Transfer reinforcement learning with composite MDPs where tasks share core dynamics but have sparse differences.
method UCB-TQL, a novel transfer RL algorithm for composite MDPs.
result Achieved a regret bound of that scales independently of the ambient dimension.
New algorithm reduces switching costs in RL beyond linear MDPs.
problem Costly policy switching in reinforcement learning.
method ELEANOR-LowSwitching algorithm for linear Bellman-complete MDPs.
result Achieves near-optimal regret with logarithmic switching cost.
Sparse Attention Guided Dynamic Value Estimation for Single-Task Multi-Scene Reinforcement Learningcs.LG
A new method for estimating joint value functions in multi-scene reinforcement learning.
problem High variance in samples for policy gradient computations in multi-scene environments.
method Sparse attention mechanism over multiple value function hypotheses to approximate the true joint value function.
result Significant improvements in reward scores and enhanced navigation efficiency across OpenAI ProcGen environments.
We propose an actor-critic, model-free, and online Reinforcement Learning (RL) framework for continuous-state continuous-action Markov Decision Processes (MDPs) when the reward is highly sparse but encompasses a high-level temporal structure. We represent this temporal structure by a finite-state machine and construct …
Kernel-UCBVI algorithm balances exploration and exploitation in metric state-action spaces.
problem Exploration-exploitation dilemma in finite-horizon reinforcement learning with metric state-action spaces.
method Kernel-UCBVI, leveraging smoothness and kernel estimators of rewards and transitions.
result First regret bound for kernel-based RL using smoothing kernels, .
Paper improves reinforcement learning in multi-scene tasks.
problem Reducing sample variance in multi-scene reinforcement learning.
method Sparse dynamic value estimation using Gaussian mixture models.
result Significant improvements in reward scores and navigation efficiency.
ETGL-DDPG improves DDPG for sparse reward control with new exploration and replay techniques.
problem Sparse reward continuous control in reinforcement learning.
method Introduces -greedy search and GDRB framework for efficient exploration and reward use.
result ETGL-DDPG outperforms DDPG and other methods on sparse-reward continuous benchmarks.
Off-Policy Evaluation for Missingness-Aware Policies in MDPs with Rewards Missing Not at Randomstat.ML
Off-policy evaluation for MNAR rewards in MDPs
problem Off-policy evaluation in MDPs with MNAR rewards
method Formalizing a reward-dependent propensity model and using future states as shadow variables
result Proposed an Fitted-Q-Evaluation-style estimator that propagates recovered rewards while allowing target policies to depend on past missingness indicators
New methods tackle robust reinforcement learning in sparse, corrupted data.
problem Tackles robust reinforcement learning in sparse, corrupted data.
method Proposes actor-critic methods with sparse robust estimator oracles.
result First non-vacuous guarantees in high-dimensional sparse MDPs with single-policy concentrability coverage.
Humans achieve efficient learning by relying on prior knowledge about the structure of naturally occurring tasks. There is considerable interest in designing reinforcement learning (RL) algorithms with similar properties. This includes proposals to learn the learning algorithm itself, an idea also known as meta learnin…
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.
We study the sparse entropy-regularized reinforcement learning (ERL) problem in which the entropy term is a special form of the Tsallis entropy. The optimal policy of this formulation is sparse, i.e.,~at each state, it has non-zero probability for only a small number of actions. This addresses the main drawback of the …
We study Exo-MDPs to reduce sample complexity in reinforcement learning.
problem Reducing sample complexity in reinforcement learning for structured MDPs.
method Introducing Exo-MDPs and proving structural equivalence to linear mixture MDPs, establishing regret bounds.
result Proved regret bound for Exo-MDPs, matching lower bounds.
Improved exploration methods for reinforcement learning with reduced sample complexity.
problem Challenges in reinforcement learning exploration in unknown environments.
method Proposed game-theoretic and trajectory entropy algorithms with improved sample complexity.
result Established statistical advantage of entropy-regularized MDPs for exploration and reduced sample complexity.
Paper establishes new lower bounds for MDPs with changing transition kernels.
problem Minimizing sample complexity and regret in non-stationary MDPs.
method Developed novel lower bounds and constructed hard MDPs.
result Proved sample complexity lower bound.
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 …
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…
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.
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 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.
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.
Online RL in Linearly -Realizable MDPs Is as Easy as in Linear MDPs If You Learn What to Ignorecs.LG
New RL method learns to skip states in linearly -realizable MDPs, simplifying to linear MDPs.
problem Online RL in episodic MDPs with linearly -realizable action-values.
method Derives a novel algorithm that learns to skip states and applies a linear MDP algorithm.
result First polynomial-sample-complexity online RL algorithm for linearly -realizable MDPs.
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))
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…
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.
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.
Reward suffices for convex MDPs, expanding RL to new problems.
problem Capturing goals as convex functions of stationary distribution.
method Reformulated as a min-max game using Fenchel duality.
result Convex MDPs require non-stationary reward functions.
Practical reinforcement learning problems are often formulated as constrained Markov decision process (CMDP) problems, in which the agent has to maximize the expected return while satisfying a set of prescribed safety constraints. In this study, we propose a novel simulator-based method to approximately solve a CMDP pr…
The paper addresses statistical estimation in MDPs with confounders using instrumental variables.
problem Statistical estimation of value functions in MDPs with unobservable confounders.
method Two-stage estimator based on instrumental variables for confounded linear MDPs.
result Established statistical properties of the two-stage estimator, including error bounds and asymptotic normality.
Study on regret minimization in deterministic MDPs.
problem Minimizing regret in deterministic reinforcement learning.
method Logarithmic regret lower bounds, leveraging graph theory and cycles.
result Explicitly quantifies the fundamental limit of performance achievable by any learning algorithm.
Paper proposes efficient sample collection strategy for RL.
problem Balancing exploration and exploitation in reinforcement learning.
method Decoupled approach with objective-specific and objective-agnostic strategies.
result Improved or novel sample complexity guarantees for various RL settings.
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.
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.
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.
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.
It has recently been shown that if feedback effects of decisions are ignored, then imposing fairness constraints such as demographic parity or equality of opportunity can actually exacerbate unfairness. We propose to address this challenge by modeling feedback effects as Markov decision processes (MDPs). First, we prop…
The paper introduces MDP homomorphic networks for faster reinforcement learning.
problem Current reinforcement learning approaches do not exploit symmetries in the joint state-action space.
method Equivariant neural networks with group-structured symmetries (reflections, rotations).
result MDP homomorphic networks converge faster than unstructured baselines on various tasks.
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.
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…
Sample Efficient Reinforcement Learning In Continuous State Spaces: A Perspective Beyond Linearitycs.LG
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.