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 Markov Decision Processes”
New algorithm minimizes regret in sparse reinforcement learning.
problem Sparse reinforcement learning with unknown sparsity.
method Doubly robust approach combining feature vectors of all actions and novel analysis.
result Regret bound of .
Paper tests Markov assumption in sequential decision making.
problem Testing the Markov assumption in sequential decision making.
method Forward-Backward Learning procedure to test MA without assuming parametric forms.
result The proposed test plays a crucial role in identifying optimal policies in complex decision processes.
Partially observable Markov decision processes (POMDPs) with continuous state and observation spaces have powerful flexibility for representing real-world decision and control problems but are notoriously difficult to solve. Recent online sampling-based algorithms that use observation likelihood weighting have shown un…
New algorithm solves uncertain Markov decision processes using Wasserstein uncertainty.
problem Solving Markov decision processes with uncertain transition probabilities.
method Distributionally robust -learning algorithm for Wasserstein uncertainty.
result Convergence of the algorithm proved and demonstrated with real data.
New method uses reinforcement learning to sample from complex data structures efficiently.
problem Constructing reliable samples from high-dimensional polytopes for goodness-of-fit tests.
method Markov decision process and reinforcement learning for sampling.
result Demonstrated scalable tools from linear algebra for theoretical guarantees in non-linear algebra context.
In this paper we propose an algorithm that builds sparse decision DAGs (directed acyclic graphs) from a list of base classifiers provided by an external learning method such as AdaBoost. The basic idea is to cast the DAG design task as a Markov decision process. Each instance can decide to use or to skip each base clas…
Paper presents an algorithm for optimal regret in communicating Markov decision processes.
problem Achieving optimal regret in Markov decision processes with a communicating assumption.
method The algorithm explicitly tracks the constant K(M) to learn optimally, balancing exploration, co-exploration, and exploitation.
result The algorithm achieves asymptotically optimal regret for communicating Markov decision processes.
Study optimality in safety-constrained Markov decision processes using asynchronous value iteration and modified Q-learning.
problem Optimality in safety-constrained Markov decision processes with multichain structure.
method Formulated as a zero-sum game, constructed asynchronous value iteration scheme and modified Q-learning algorithm.
result Resolved Bellman's principle of optimality for multichain Markov decision processes and provided learning algorithms.
Advances in mobile computing technologies have made it possible to monitor and apply data-driven interventions across complex systems in real time. Markov decision processes (MDPs) are the primary model for sequential decision problems with a large or indefinite time horizon. Choosing a representation of the underlying…
Develops an actor-critic algorithm for risk-sensitive Markov decision processes.
problem Risk-sensitive cost criterion in Markov decision processes.
method Actor-critic algorithm with function approximation.
result Asymptotic convergence of the actor-critic algorithm.
Overview of risk-sensitive Markov decision processes with Optimized Certainty Equivalent.
problem Optimizing decision-making under risk in Markov processes.
method Analyzes risk-sensitive criteria using Optimized Certainty Equivalent, including entropic risk and Conditional Value-at-Risk.
result Conditions for the existence of optimal policies and solution procedures are provided.
Bayesian approach for constructing and rebalancing sparse index-tracking portfolios.
problem Sparse tracking of a reference index with uncertainty quantification.
method Sparse linear regression with Laplace prior, empirical-Bayes calibration, Langevin-type MCMC, threshold-based rules.
result Posterior uncertainty on tracking error, portfolio composition, and rebalancing moves.
Algorithm finds safe zones in policy Markov Decision Processes to limit trajectory escape.
problem Finding safe zones in policy Markov Decision Processes to limit trajectory escape.
method Bi-criteria approximation learning algorithm with polynomial sample complexity.
result Achieves almost 2 approximation for both escape probability and safe zone size.
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.
Risk measures applied to dynamic Markov processes with varying risk aversion.
problem Investigating dynamic risk measures in Markov decision processes with varying risk aversion.
method Distributional viewpoint on law-invariant convex risk measures, applied to Markov decision processes with latent costs and random actions.
result Existence of optimal policies in finite and infinite time horizons under mild assumptions.
We address the problem of inverse reinforcement learning in Markov decision processes where the agent is risk-sensitive. In particular, we model risk-sensitivity in a reinforcement learning framework by making use of models of human decision-making having their origins in behavioral psychology, behavioral economics, an…
Bayesian method infers local rules for collective animal movement.
problem Learn local rules governing long-term group behaviors.
method Bayesian Inverse Reinforcement Learning with Linearly-Solvable Markov Decision Process.
result Recover true costs and find value of collective movement.
The paper tackles batch policy learning in Markov Decision Processes, focusing on average reward maximization.
problem Maximizing long-term average reward in Markov Decision Processes with batch learning.
method Doubly robust estimator for average reward, optimization algorithm for optimal policy, finite-sample regret guarantee.
result The proposed method achieves semiparametric efficiency and provides a finite-sample regret guarantee.
New algorithm identifies best policy in MDPs faster.
problem Identifying the best policy in Markov Decision Processes.
method Problem-dependent lower bound and first algorithm with instance-specific sample complexity.
result First algorithm with reduced exploration rate for faster convergence.
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, …
We develop robust Markov Decision Processes with risk measures for uncertain environments.
problem Uncertainty in Markov Decision Processes and its impact on risk measures.
method Formulation as a Stackelberg game, robust cost and value iterations, existence of optimal policies.
result Existence of deterministic optimal policies for robust optimization and risk measures.
Q-learning for average cost MDPs gets a concentration bound.
problem Finding bounds for Q-learning in average cost MDPs.
method Derives a concentration bound using shortest path problem equivalence.
result Numerical comparison with relative value iteration shows the bound's effectiveness.
New Q-learning method achieves optimal sample complexity for average-reward problems.
problem Challenges in achieving optimal sample complexity for average-reward Q-learning.
method Synchronous and asynchronous Q-learning with a new contraction principle.
result Optimal sample complexity guarantees.
We introduce Threatened Markov Decision Processes (TMDPs) as an extension of the classical Markov Decision Process framework for Reinforcement Learning (RL). TMDPs allow suporting a decision maker against potential opponents in a RL context. We also propose a level-k thinking scheme resulting in a novel learning approa…
New methods reduce computational cost for Gaussian Markov Random Fields with sparse constraints.
problem Inference and simulation of GMRFs are computationally prohibitive with many constraints.
method Proposes a basis transformation into blocks of constrained and non-constrained subspaces.
result Significantly outperforms existing alternatives in computational cost.
This paper analyzes risk-sensitive reinforcement learning with Conditional Value-at-Risk (CVaR) for robust Markov Decision Processes.
problem Risk-sensitive reinforcement learning for robust Markov Decision Processes (RMDPs) with state-action-dependent ambiguity sets.
method The paper establishes a connection between robustness and risk sensitivity, defining a new risk measure NCVaR and proposing value iteration algorithms.
result The proposed approach using NCVaR optimization and value iteration algorithms can solve problems with state-action-dependent ambiguity sets.
We characterize value functions in partially observable MDPs as semi-algebraic sets.
problem Understanding feasible value functions in partially observable Markov decision processes.
method Characterization of feasible value functions as semi-algebraic sets defined by polynomial inequalities.
result The feasible set of value functions in POMDPs is a semi-algebraic set, not a polytope as in MDPs.
New RL framework models continuous-time dynamics using neural ODEs.
problem Modeling continuous-time dynamics in semi-Markov decision processes.
method Model-based reinforcement learning with neural ODEs.
result High-performing policies developed with minimal data.
Study minimax-optimal rates for offline decision-making with function approximation.
problem Statistical complexity of offline decision-making with function approximation.
method Near minimax-optimal rates for stochastic contextual bandits and Markov decision processes, using pseudo-dimension and behavior policy.
result Established performance limits and new characterization of behavior policy.
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.
The paper tackles robust policy learning in MDPs using statistical methods.
problem Offline data-driven sequential decision making in MDPs.
method Evaluates policies using average rewards centered at policy-induced stationary distributions. Developed a statistically efficient method for estimating robust optimal policies.
result Established a rate-optimal regret bound up to a logarithmic factor.
Modeling driver trajectories using inverse reinforcement learning and random utility.
problem Modeling rational driver behavior in road networks from sparse sensor data.
method Apply random utility theory to model unknown reward function, introduce extended state, and use Markov decision process.
result Maximum entropy inverse reinforcement learning is a special case of the proposed approach.
Paper tackles identifying an odd arm in a multi-armed bandit with restless Markov processes and trembling hand.
problem Identifying an odd arm in a multi-armed bandit with restless Markov processes and trembling hand.
method Derive asymptotic lower bound on expected time to identify the odd arm, stitch together parameterised solutions to MDPs.
result First known asymptotic lower bound on expected time to identify the odd arm, with vanishing error probability.
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.
We present a new model-based reinforcement learning algorithm, Cooperative Prioritized Sweeping, for efficient learning in multi-agent Markov decision processes. The algorithm allows for sample-efficient learning on large problems by exploiting a factorization to approximate the value function. Our approach only requir…
Sampling Decisionscs.LG
Introduces DF framework for sampling decisions from target distributions.
problem Sampling from target distributions with additional guidance.
method DF framework based on MDP and Path Integral Diffusion.
result DF enhances guided sampling across various applications.
We develop algorithms with low regret for learning episodic Markov decision processes based on kernel approximation techniques. The algorithms are based on both the Upper Confidence Bound (UCB) as well as Posterior or Thompson Sampling (PSRL) philosophies, and work in the general setting of continuous state and action …
New RL approach tackles constrained Markov decision processes.
problem Applying RL to physical systems with safety constraints.
method Formulated as a Constrained Markov Decision Process (CMDP), introduced a safe policy improvement method.
result Agent learns to maximize returns while satisfying constraints.
Develops new reinforcement learning methods for complex constrained decision-making problems.
problem Complex constrained decision-making problems with a continuum of constraints.
method Proposes semi-infinitely constrained Markov decision processes (SICMDPs) and two reinforcement learning algorithms: SI-CRL and SI-CPO.
result Demonstrates the effectiveness of SI-CRL and SI-CPO in solving complex sequential decision-making tasks.
The paper introduces a method to learn Markov state abstractions for reinforcement learning.
problem Learning Markov state representations in complex environments.
method The paper introduces a novel set of conditions and a training procedure combining inverse model estimation and temporal contrastive learning.
result The approach learns representations that capture the underlying structure of the domain and improve sample efficiency.
We introduce a new formulation of the Hidden Parameter Markov Decision Process (HiP-MDP), a framework for modeling families of related tasks using low-dimensional latent embeddings. Our new framework correctly models the joint uncertainty in the latent parameters and the state space. We also replace the original Gaussi…
New methods improve temporal difference learning for policy evaluation in Markov decision processes.
problem Improving temporal difference learning for policy evaluation in Markov decision processes.
method Introduced variance-reduced forms of stochastic approximation to achieve non-asymptotic, instance-dependent optimality.
result Temporal difference learning is strictly suboptimal, but variance-reduced forms achieve optimality up to logarithmic factors.
Algorithm learns mixtures of Markov chains and MDPs from short trajectories.
problem Learning mixtures of Markov chains and MDPs from short unlabeled trajectories.
method Subspace estimation, spectral clustering, EM algorithm, model estimation, classification.
result 96.6% average accuracy on a mixture of two MDPs in gridworld, outperforming EM algorithm with random initialization.
This work extends reinforcement learning to handle non-cumulative objectives.
problem Optimizing functions of rewards rather than their sum in decision processes.
method Mapping NCMDPs to standard MDPs for reinforcement learning.
result Reinforcement learning techniques can be applied to NCMDPs.
Maximize to Explore integrates RL components for efficient policy discovery.
problem Balancing exploration and exploitation in online RL with general function approximators.
method Integrates estimation, planning, and exploration into a single objective function.
result Achieves sublinear regret for MDPs and MGs with general function approximations.
Studies on massive open online courses (MOOCs) users discuss the existence of typical profiles and their impact on the learning process of the students. However defining the typical behaviors as well as classifying the users accordingly is a difficult task. In this paper we suggest two methods to model MOOC users behav…
A new method for risk-averse decision-making in Markov processes with improved regret bounds.
problem Risk-averse decision-making in Markov processes.
method Introduces mini-batch measures and multipattern risk-averse problems in a feature-based -learning method.
result Proves a high-probability regret bound of for the -learning method.