While designing the state space of an MDP, it is common to include states that are transient or not reachable by any policy (e.g., in mountain car, the product space of speed and position contains configurations that are not physically reachable). This leads to defining weakly-communicating or multi-chain MDPs. In this…
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,742 papers · 148 categories
Trend · papers per month
48 results for “communicating 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.
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.
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.
New method reduces regret and communication costs in federated Q-learning.
problem Worst-case regret and communication cost bounds in federated Q-learning.
method Gap-dependent analysis leveraging MDP structures.
result Achieves -type regret and communication cost bounds.
This work improves Q-learning for average-reward MDPs, reducing sample and communication complexities in federated settings.
problem Improving sample complexity of Q-learning for average-reward MDPs.
method Simple Q-learning algorithm with carefully chosen parameters for both single-agent and federated scenarios.
result Established first federated Q-learning algorithm for average-reward MDPs with provable efficiency in sample and communication complexities.
We introduce SCAL, an algorithm designed to perform efficient exploration-exploitation in any unknown weakly-communicating Markov decision process (MDP) for which an upper bound on the span of the optimal bias function is known. For an MDP with states, actions and possible next states, we prove a …
The paper tackles cooperative RL with function approximation, achieving near-optimal learning with limited communication.
problem Cooperative multi-agent reinforcement learning with function approximation.
method Careful message-passing and cooperative value iteration.
result Achieving near-optimal no-regret learning with limited communication in cooperative multi-agent settings.
One of the most significant bottleneck in training large scale machine learning models on parameter server (PS) is the communication overhead, because it needs to frequently exchange the model gradients between the workers and servers during the training iterations. Gradient quantization has been proposed as an effecti…
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…
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.
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))
MetaCURL tackles non-stationary MDPs with optimal dynamic regret.
problem Online learning in non-stationary Markov decision processes.
method MetaCURL uses a meta-algorithm with multiple black-box algorithms and a sleeping expert framework.
result Achieves optimal dynamic regret without prior knowledge of MDP changes.
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…
This paper sets communication complexity bounds for distributed RL.
problem Establishing minimum communication requirements for distributed RL.
method Information-theoretic lower bounds and algorithm development.
result Developed algorithms achieving optimal risk up to logarithmic factors.
Agents collaboratively learn optimal policies in MDPs with limited capabilities.
problem Learning optimal policies in MDPs with heterogeneous agents and limited communication.
method Introduced concepts of leakage probabilities and proposed Federated-Q protocol (FedQ) for collaborative learning.
result FedQ protocol effectively aggregates knowledge and modifies learning problems for further training.
PAC Guarantees for Cooperative Multi-Agent Reinforcement Learning with Restricted Communicationcs.LG
We develop model free PAC performance guarantees for multiple concurrent MDPs, extending recent works where a single learner interacts with multiple non-interacting agents in a noise free environment. Our framework allows noisy and resource limited communication between agents, and develops novel PAC guarantees in this…
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.
In this paper, we study a multi-step interactive recommendation problem, where the item recommended at current step may affect the quality of future recommendations. To address the problem, we develop a novel and effective approach, named CFRL, which seamlessly integrates the ideas of both collaborative filtering (CF) …
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…
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.
Improved analysis of UCRL2 with empirical Bernstein inequality reduces exploration-exploitation regret.
problem Exploration-exploitation in communicating Markov Decision Processes.
method Analysis of UCRL2 with Empirical Bernstein inequalities (UCRL2B).
result Regret bound of for UCRL2B.
This paper presents a unifying framework for reinforcement learning and planning.
problem Sequential decision making in AI, formalized as MDP optimization.
method A unifying algorithmic framework (FRAP) for reinforcement learning and planning.
result Identifies common dimensions in MDP planning and learning algorithms.
Study non-rectangular robust MDPs for average-reward, finding optimal policies and transient values.
problem Non-rectangular robust Markov decision processes under average-reward criterion.
method Proves history-dependent policies are robust-optimal, introduces transient-value framework, constructs epoch-based policy.
result Existence and properties of robust optimal policies, transient value bounds.
Federated Q-Learning achieves linear regret speedup with low communication cost.
problem Achieving linear regret speedup in federated reinforcement learning without high communication costs.
method Proposed two federated Q-Learning algorithms: FedQ-Hoeffding and FedQ-Bernstein, using event-triggered synchronization, novel step size selection, and concentration inequalities.
result Total regrets achieve linear speedup compared to single-agent counterparts with logarithmic communication cost.
We study model-based reinforcement learning in an unknown finite communicating Markov decision process. We propose a simple algorithm that leverages a variance based confidence interval. We show that the proposed algorithm, UCRL-V, achieves the optimal regret up to logarithmic factors…
Paper establishes lower bounds and optimal algorithms for deployment-efficient RL.
problem Deployment efficiency in reinforcement learning.
method Optimization with constraints, lower bounds, algorithms.
result Established optimal algorithms for deployment-efficient RL.
We explore the use of Evolution Strategies (ES), a class of black box optimization algorithms, as an alternative to popular MDP-based RL techniques such as Q-learning and Policy Gradients. Experiments on MuJoCo and Atari show that ES is a viable solution strategy that scales extremely well with the number of CPUs avail…
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 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.
Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningstat.ML
New RL algorithms reduce costs for single-agent and federated learning.
problem Minimizing costs in RL and federated RL settings.
method Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost algorithms.
result First algorithms to achieve low burn-in and logarithmic switching costs.
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…
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 …
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.
Improved stochastic Halpern iteration for fixed-point approximation in normed spaces.
problem Approximating fixed-points of nonexpansive and contractive operators in normed finite-dimensional spaces.
method Stochastic Halpern iteration with minibatch, analyzing oracle complexity.
result Improved oracle complexity for nonexpansive operators, with a lower bound of .
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…
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.
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.
New lower bound shows RL with linear approximations is computationally hard.
problem Computational hardness in reinforcement learning with linear function approximation.
method Reduction from Unique-Sat to MDPs with linear optimal value functions.
result No randomized polynomial time algorithm exists for RL with linear function approximation unless NP=RP.
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.
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.
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.