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.
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,657 papers · 148 categories
Trend · papers per month
48 results for “discounted 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.
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))
New RL difficulty shown for discounted settings.
problem Difficulty in reinforcement learning with discounted rewards.
method Adapted Wang et al. (2020) construction to 2-state MDP.
result Learning impossible even with infinite data in discounted setting.
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.
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.
Faster algorithms for solving multichain MDPs under average-reward criterion.
problem Navigating towards the best connected component in multichain MDPs.
method Developed algorithms to better solve the navigational subproblem, achieving faster convergence rates.
result Improved rates of convergence and sharper complexity measures for multichain MDPs.
NVMDP framework tackles non-stationary MDPs with varying discount rates.
problem Challenges in non-stationary environments and infinite-horizon formulations for reinforcement learning.
method Introduces NVMDP framework that accommodates non-stationarity and varying discount rates.
result NVMDPs provide a flexible mechanism to shape optimal policies without altering state or action spaces.
Improved RL algorithm with linear MDPs for offline learning with partial data coverage.
problem Efficient offline RL with linear MDPs under partial data coverage.
method Primal-dual algorithm with sample complexity.
result First computationally efficient algorithm with sample complexity for offline RL with linear MDPs under partial data coverage.
Entropy-regularized NPG methods converge linearly in discounted MDPs.
problem Theoretical limitations of NPG methods in reinforcement learning.
method Entropy regularization in conjunction with NPG methods for discounted MDPs.
result Entropy-regularized NPG methods converge linearly in discounted MDPs.
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.
The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysiscs.LG
Optimal sample complexity analysis for plug-in approach in average-reward MDPs.
problem Learning optimal policies in average-reward MDPs with a generative model.
method Plug-in approach that constructs a model estimate and computes an optimal policy.
result Optimal sample complexities for the plug-in approach without prior knowledge of problem parameters.
Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processescs.LG
New RL theory reduces sample complexity for mixing MDPs.
problem Optimal sample complexity for reinforcement learning in mixing MDPs.
method Regeneration-type ideas to analyze mixing times.
result Optimal sample complexity depends on mixing time, not just discount factor.
New algorithm learns optimal policies with minimal memory and time.
problem Learning optimal policies in discounted MDPs with short burn-in time.
method Variance reduction and adaptive policy switching.
result First regret-optimal model-free algorithm with low burn-in time.
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 algorithms identify best policies in discounted linear MDPs efficiently.
problem Identifying the best policy in discounted linear MDPs with limited samples.
method Derive lower bounds and devise simple yet near-optimal algorithms.
result Upper bound on sample complexity matches existing bounds.
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…
Study risk-sensitive reinforcement learning with entropic risk measures and generative models.
problem Risk-sensitive reinforcement learning in discounted MDPs with recursive entropic risk measures.
method Introduced Model-Based ERM -Value Iteration (MB-RS-QVI) and derived PAC bounds on sample complexity for value and policy learning.
result PAC bounds show exponential dependence on , with tight bounds in and .
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.
New bounds for learning near-optimal policies in CMDPs with constraints.
problem Optimizing policies in CMDPs with constraints.
method Model-based algorithm addressing relaxed and strict feasibility.
result Near-optimal sample complexity bounds for CMDPs.
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.
We introduce and analyze a form of variance-reduced -learning. For -discounted MDPs with finite state space and action space , we prove that it yields an -accurate estimate of the optimal -function in the -norm using $\mathcal{O} \left(\left(\frac{D}{ ε^2 (1-γ)^3} \ri…
We consider model-free reinforcement learning for infinite-horizon discounted Markov Decision Processes (MDPs) with a continuous state space and unknown transition kernel, when only a single sample path under an arbitrary policy of the system is available. We consider the Nearest Neighbor Q-Learning (NNQL) algorithm to…
On the Sample Complexity of Discounted Reinforcement Learning with Optimized Certainty Equivalentscs.LG
Study risk-sensitive reinforcement learning with optimized certainty equivalents.
problem Risk-sensitive reinforcement learning in finite discounted MDPs.
method Analyzed a simple model-based approach and derived PAC sample complexity bounds.
result Established tight sample complexity bounds for value and policy learning.
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 paper improves Thompson Sampling for complex decision-making problems.
problem Learning in infinite-horizon discounted decision processes with unknown parameters.
method Developed a general canonical probability space and new metrics for analyzing adaptive learning algorithms.
result Thompson Sampling achieves complete learning in complex decision-making problems.
New offline RL method handles average-reward MDPs with single-policy coverage.
problem Challenges in offline reinforcement learning due to distribution shift and non-uniform coverage.
method Develops an algorithm based on pessimistic discounted value iteration with quantile clipping.
result First fully single-policy sample complexity bound for average-reward offline RL.
In reinforcement learning, the discount factor controls the agent's effective planning horizon. Traditionally, this parameter was considered part of the MDP; however, as deep reinforcement learning algorithms tend to become unstable when the effective planning horizon is long, recent works refer to as a hyper-p…
We study the online estimation of the optimal policy of a Markov decision process (MDP). We propose a class of Stochastic Primal-Dual (SPD) methods which exploit the inherent minimax duality of Bellman equations. The SPD methods update a few coordinates of the value and policy estimates as a new state transition is obs…
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.
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.
Model-free reinforcement learning is known to be memory and computation efficient and more amendable to large scale problems. In this paper, two model-free algorithms are introduced for learning infinite-horizon average-reward Markov Decision Processes (MDPs). The first algorithm reduces the problem to the discounted-r…
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.
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 .
New findings reveal discount regularization can be seen as a strong prior, leading to poor performance in unevenly sampled data.
problem Discount regularization leads to poor performance in unevenly sampled data.
method Equivalence theorem showing discount regularization as a strong prior, setting regularization parameters locally for individual state-action pairs.
result Discount regularization can be seen as a strong prior, leading to poor performance in unevenly sampled data.
Efficiently selects seed nodes to maximize content influence in unknown social networks.
problem Maximizing content spread in social networks with unknown network model.
method Formulated as an infinite-horizon discounted MDP, uses model-based reinforcement learning to select seed users adaptively.
result Established a regret bound of for the algorithm.
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…
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.
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, …
Study on policy testing in MDPs with lower bounds and new algorithm.
problem Deciding if policy value exceeds a threshold with limited samples.
method Derived lower bound, proposed new algorithm, reformulated problem, used policy optimization in reversed MDP.
result New algorithm outperforms existing methods in policy testing.
We consider the problem of learning the optimal action-value function in the discounted-reward Markov decision processes (MDPs). We prove a new PAC bound on the sample-complexity of model-based value iteration algorithm in the presence of the generative model, which indicates that for an MDP with N state-action pairs a…
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.
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.
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.
In this work, we provide theoretical guarantees for reward decomposition in deterministic MDPs. Reward decomposition is a special case of Hierarchical Reinforcement Learning, that allows one to learn many policies in parallel and combine them into a composite solution. Our approach builds on mapping this problem into a…
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 …
Algorithm identifies best policy in MDPs with adaptive sampling.
problem Best policy identification in discounted MDPs with limited samples.
method Derive lower and upper bounds on sample complexity, design KLB-TS algorithm.
result KLB-TS algorithm achieves nearly-optimal sample allocation.
Study improves reinforcement learning for stable long-term performance.
problem Distributionally robust average-reward reinforcement learning for stable long-term performance.
method Proposes two algorithms to achieve near-optimal sample complexity.
result Achieves a sample complexity of for estimating optimal policy and robust average reward.