New method for estimating and optimizing MDPs without stationarity.
problem Challenges in offline contextual MDP estimation without stationarity.
method Introduces a new adaptive estimation and cost optimization approach for contextual MDPs.
result First robust, theoretically backed method for offline contextual MDP estimation.
New algorithm matches best regret bound for tabular Contextual Bandit problems.
problem Learning from observations in uncertain environments.
method A minor variant of a reinforcement learning algorithm for MDPs.
result The algorithm matches the best possible regret bound i l d e O ( S A T ) ilde O (\sqrt{SAT}) i l d e O ( S A T ) for tabular Contextual Bandit problems. Agent learns reward function from demonstrations in contextual MDPs.
problem Learn reward function from demonstrations in unseen contexts.
method Formulated as convex optimization, proposed algorithm computes subgradients.
result Zero-shot transfer demonstrated in dynamic treatment regime.
We consider the recently proposed reinforcement learning (RL) framework of Contextual Markov Decision Processes (CMDP), where the agent interacts with a (potentially adversarial) sequence of episodic tabular MDPs. In addition, a context vector determining the MDP parameters is available to the agent at the start of eac…
Paper studies linear CMDPs, improving sample complexity for both models.
problem Improving sample complexity for linear CMDPs.
method Proposes novel model-based algorithms for two linear function approximation models.
result Guaranteed ε-suboptimality gap with desired polynomial sample complexity.
Efficient algorithm for learning from indirect feedback in complex decision-making scenarios.
problem Learning from indirect feedback in realistic scenarios with personalized mechanisms.
method IGW algorithm for policy optimization, extending reward-estimator construction from single-step to multi-step.
result Achieves sublinear regret guarantee for contextual episodic MDPs with personalized feedback.
Paper tackles online learning in large MDPs with low Bellman rank using AVE algorithm.
problem Online learning of MDPs with large state spaces.
method Develops AVE algorithm inspired by OLIVE, using contextual bandit problems and elimination steps.
result Achieves n \sqrt{n} n -regret for learning optimal value function in MDPs with function approximation and low Bellman rank. Efficient RL for linear MDPs with unknown transitions.
problem Long planning horizons and unknown state transitions in linear mixture MDPs.
method Horizon-free algorithm using weighted least squares with variance and uncertainty awareness.
result Achieves optimal regret up to logarithmic factors.
We consider a reinforcement learning (RL) setting in which the agent interacts with a sequence of episodic MDPs. At the start of each episode the agent has access to some side-information or context that determines the dynamics of the MDP for that episode. Our setting is motivated by applications in healthcare where ba…
We study the sample complexity of model-based reinforcement learning (henceforth RL) in general contextual decision processes that require strategic exploration to find a near-optimal policy. We design new algorithms for RL with a generic model class and analyze their statistical properties. Our algorithms have sample …
New benchmarks for algorithm control using RL.
problem Optimizing algorithm performance through online hyperparameter tuning.
method Formulated as a contextual MDP, solved with reinforcement learning.
result Reinforcement learning outperforms black-box approaches for longer sequences.
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.
New model selects robustly in adversarial reinforcement learning with unknown corruption.
problem Adversarial corruption in reinforcement learning with unknown total corruption amount.
method Model selection approach for finite-horizon tabular and linear MDPs.
result First worst-case optimal bound without knowledge of total corruption.
CB-RL solves complex decision-making problems with contextual information and exogenous events.
problem Optimal policy in strategic decision-making problems that depend on environmental configuration and exogenous events.
method Contextual Bilevel Reinforcement Learning (CB-RL) with a stochastic Hyper Policy Gradient Descent (HPGD) algorithm.
result Demonstrated convergence and performance of the HPGD algorithm for reward shaping and tax design.
New approach turns optimal stationary RL into non-stationary RL without prior knowledge.
problem Optimal RL in non-stationary environments without prior knowledge of non-stationarity.
method Black-box reduction of optimal stationary RL algorithms to non-stationary RL.
result Achieves optimal dynamic regret bounds in various RL settings.
Improved Thompson Sampling reduces regret in contextual bandits and reinforcement learning.
problem Thompson Sampling's exploration is insufficient in some contexts.
method Developed Feel-Good Thompson Sampling to address exploration issues.
result Feel-Good Thompson Sampling reduces regret compared to standard Thompson Sampling.
Minimax PAC bounds for learning in exogenous contextual MDPs
problem PAC learning in tabular discounted Markov decision processes with exogenous i.i.d. contexts
method Variance-reduced algorithm for policy evaluation, best-value estimation, and best-policy extraction
result Minimax optimal sample complexity
New algorithm reduces regret in RL with adversarial corruption.
problem Adversarial corruption in reinforcement learning.
method Uncertainty-weighted least-squares regression and weighted uncertainty estimator.
result Achieves regret of i l d e O ( T + ζ ) ilde{O}(\sqrt{T} + ζ) i l d e O ( T + ζ ) for contextual bandits. New framework handles dynamic contexts in reinforcement learning.
problem Learning in environments where contexts change over time.
method Dynamic Contextual Markov Decision Processes (DCMDPs) with logistic aggregation.
result Upper-confidence-bound style algorithm with regret bounds.
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.
Efficient algorithm for CMDPs reduces to offline density estimation.
problem Offline learning for CMDPs with horizon H.
method Reduction to offline density estimation, layerwise exploration-exploitation tradeoff.
result First efficient and near-optimal reduction from CMDPs to offline density estimation.
Paper develops a new estimator for MDPs' risk functionals with lower variance and bias.
problem Estimating the distribution of returns in MDPs with high variance and bias.
method Developed a doubly robust (DR) estimator for the CDF of returns in MDPs, incorporating model-based estimation to mitigate variance issues.
result The DR estimator achieves lower variance and bias compared to IS estimators, and matches minimax lower bounds.
Study off-policy evaluation and learning in dynamic pricing with context.
problem Dynamic personalized pricing and operations management problems with high-dimensional user types.
method Formalize causal structure, leverage single time-step evaluation, estimate marginal MDP.
result Improved out-of-sample policy performance in dynamic and capacitated pricing.
Study batch reinforcement learning methods for personalized medical treatments.
problem Batch reinforcement learning for personalized medical treatments.
method Direct policy learning and model-based learning approaches.
result Model-based learning is impossible with finite model classes but feasible with relaxed conditions.
New algorithm reduces regret for linear bandits with unknown noise variance.
problem Finding optimal actions in linear bandits with varying noise variance.
method Adaptive algorithm with Freedman-type concentration inequality and multi-layer structure.
result Achieves i l d e O ( d ∑ k = 1 K σ k 2 + d ) ilde{O}(d \sqrt{\sum_{k = 1}^K σ_k^2} + d) i l d e O ( d ∑ k = 1 K σ k 2 + d ) regret for linear bandits. In crowd labeling, a large amount of unlabeled data instances are outsourced to a crowd of workers. Workers will be paid for each label they provide, but the labeling requester usually has only a limited amount of the budget. Since data instances have different levels of labeling difficulty and workers have different r…
A new offline RL framework unifies imitation learning and vanilla offline RL.
problem Learning from expert datasets without active data collection.
method A new offline RL framework that interpolates between imitation learning and vanilla offline RL, using a weak concentrability coefficient and a lower confidence bound algorithm.
result LCB algorithm achieves a faster rate of 1 / N 1/N 1/ N for nearly-expert datasets, and is adaptively optimal for the entire data composition range. This paper explains why distributional reinforcement learning is better than vanilla RL using small-loss bounds.
problem Understanding when and why distributional reinforcement learning (DistRL) is superior to vanilla reinforcement learning (RL).
method The paper uses small-loss bounds to explain the benefits of DistRL, proposing algorithms and proving bounds for different RL settings.
result Distributional reinforcement learning (DistRL) outperforms vanilla RL when optimal costs are small, as shown by small-loss bounds.
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 O ( H 3 / 2 d K ) O(H^{3/2}d\sqrt{K}) O ( H 3/2 d K ) regret bound for Exo-MDPs, matching lower bounds. 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 Ω ( ( H 3 S A / ε 2 ) log ( 1 / δ ) ) Ω((H^3SA/ε^2)\log(1/δ)) Ω (( H 3 S A / ε 2 ) log ( 1/ δ )) sample complexity lower bound. ARL algorithm reduces adversarial MDP to bandit problems for reliable policy learning.
problem Learning reliable policies in non-stationary, adversarial MDPs.
method Adversarial Reinforcement Learning (ARL) algorithm that converts MDP to a sequence of adversarial bandit problems.
result Achieves optimal regret bound of O ( S A T H 3 ) O(\sqrt{SATH^3}) O ( S A T H 3 ) . 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 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.
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…
A new method for CMDP solving without compromising safety constraints.
problem Solving CMDP problems while adhering to safety constraints.
method Decomposition into reconnaissance and planning MDPs.
result Achieves safe policies for any safety constraint set.
RL applied to finance tasks, highlighting challenges and future directions.
problem Decision-making tasks in finance using RL.
method Meta-analysis of RL applications, identifying challenges and proposing future directions.
result Challenges in RL performance and future research directions.
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 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.
New RL method learns to skip states in linearly q π q^π q π -realizable MDPs, simplifying to linear MDPs.
problem Online RL in episodic MDPs with linearly q π q^π q π -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 q π q^π q π -realizable MDPs. 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.
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))
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.
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.