Pessimistic Minimax Value Iteration finds efficient NE policies from offline data.
problem Finding an approximate Nash equilibrium in offline Markov games with non-uniform coverage.
method Pessimistic Minimax Value Iteration (PMVI) constructs pessimistic value function estimates and solves NEs.
result Established a nearly minimax optimal result for offline Markov games with function approximation.
Papers learn from data to make decisions without interacting, improving on previous methods.
problem Achieving optimal decision-making from offline data with non-linear function approximation.
method Pessimistic Nonlinear Least-Square Value Iteration (PNLSVI) with three innovative components.
result Achieves minimax optimal instance-dependent regret for non-linear function approximation.
Study tight offline learning bounds for linear MDPs using variance information.
problem Understanding statistical limits with linear function representations in offline reinforcement learning.
method Variance-aware pessimistic value iteration (VAPVI) that reweights Bellman residuals based on estimated variances.
result Improved offline learning bounds expressed in terms of system quantities.
Pessimistic Q-learning improves sample efficiency in offline reinforcement learning.
problem Insufficient coverage and sample scarcity in offline reinforcement learning datasets.
method Pessimistic Q-learning algorithm for offline reinforcement learning, focusing on variance reduction.
result Near-optimal sample complexity achieved with the proposed algorithm.
A new algorithm for offline RL with trajectory-wise reward reduces bias and variance errors.
problem Offline RL with trajectory-wise reward incurs large bias and variance errors.
method PARTED algorithm that decomposes trajectory return into proxy rewards and performs pessimistic value iteration.
result PARTED achieves provably efficient suboptimality bounds in general MDPs with trajectory-wise reward.
Study risk-sensitive RL in offline settings, improving efficiency and accuracy.
problem Efficiently derive near-optimal policies for risk-sensitive RL using offline data.
method Introduced two provably sample-efficient algorithms for risk-sensitive offline RL in linear MDPs.
result First provably efficient risk-sensitive offline RL algorithms.
Proposes Optimistic Pessimistically Initialised Q-Learning (OPIQ) for better exploration in RL.
problem Pessimistic initialisation of Q-values in deep RL leads to poor exploration performance.
method Augments pessimistically initialised Q-values with count-based bonuses to ensure optimism.
result OPIQ outperforms non-optimistic DQN variants in hard exploration tasks.
New algorithm identifies near-optimal policies in adversarial distributed RL settings.
problem Adversarial agents in distributed RL settings that can collude and report arbitrary data.
method Weighted-Clique algorithm for robust mean estimation from batches, combined with novel distributed algorithms.
result Achieves superior robustness guarantees and near-optimal sample complexities in both offline and online settings.
Paper tackles robust decision-making from multiple sites with shared structure.
problem Learning robust sequential decisions from heterogeneous multi-site datasets.
method Group-Robust MDPs with d-rectangular uncertainty sets, feature-wise worst-case aggregation, and cluster-level pooling.
result Proves suboptimality bound for robust planning policy under robust partial coverage assumption.
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.
Pessimistic RL algorithm improves offline RL performance.
problem Insufficient dataset coverage in offline RL.
method Proposes a pessimistic variant of value iteration (PEVI) with a penalty function.
result Establishes upper bound on suboptimality for general MDPs, matching lower bound.
Pessimistic estimator improves multi-objective policy optimization.
problem Optimizing multi-objective policies from existing data.
method Pessimistic estimator based on inverse propensity scores (IPS).
result Pessimistic estimator outperforms naive IPS estimator in theory and experiments.
Paper tackles RLHF with DCPPO method, proving near-optimal suboptimality.
problem Challenges in offline RLHF with limited human feedback and bounded rationality.
method DCPPO method involving three stages: MLE, reward function recovery, and pessimistic value iteration.
result DCPPO's suboptimality almost matches classical pessimistic offline RL in terms of distribution shift and dimension.
A new method learns robust policies from offline data with latent structures.
problem Conservative policies under unrealistic dynamics shifts.
method d-RRMDP framework with f f f -divergence regularization and R2PVI algorithm. result R2PVI learns robust policies with superior computational efficiency.
Q-Distribution Guided Q-Learning corrects overestimation of uncertain OOD actions in offline RL.
problem Overestimation of Q-values for out-of-distribution actions in offline reinforcement learning.
method QDQ applies a pessimistic adjustment to Q-values in uncertain OOD regions based on a consistency model.
result QDQ improves performance on the D4RL benchmark and achieves significant improvements across many tasks.
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.
BCPO optimizes offline RL policies by converting uncertainty into conservative bounds.
problem Offline RL's fragility under distribution shifts and model errors.
method Bayesian approach with credible lower bounds and KL regularization.
result BCPO yields an uncertainty-calibrated policy that avoids exploiting model errors.
Proposes DRRO to mitigate over-optimization in RLHF from human feedback.
problem Over-optimization due to reward misspecification in RLHF.
method Wasserstein distributionally robust regret optimization (DRRO).
result DRRO mitigates over-optimization more effectively than existing baselines.
Extends linear MDP to handle nonlinear rewards.
problem Restrictive linear MDP assumption limits real-world applicability.
method Proposes Generalized Linear MDP (GLMDP) with GLMs for rewards.
result Develops offline RL algorithms achieving suboptimality guarantees.
Study proposes a new risk measure for optimal portfolio allocation.
problem Challenges in estimating optimal portfolios based on pessimistic risk.
method Introduces uniform pessimistic risk and computational algorithm.
result Demonstrates the usefulness of the proposed risk and portfolio model with real data analysis.
Efficient offline reinforcement learning with neural networks using differentiable function approximation.
problem Statistical efficiency of offline reinforcement learning with function approximators.
method Pessimistic fitted Q-learning (PFQL) and differentiable function approximation.
result Provably efficient offline reinforcement learning with differentiable function approximation.
A new reinforcement learning framework separates users into risk-tolerant and risk-averse groups for better performance.
problem Improving performance for risk-averse users in reinforcement learning.
method Introducing a tiered reinforcement learning approach with two policies: π e x t O π^{ ext{O}} π e x t O and π e x t E π^{ ext{E}} π e x t E . result Achieving constant regret for risk-averse users, independent of the number of episodes.
Paper tackles constrained bandit problems with a new learning framework.
problem Optimizing a black-box reward function subject to a black-box constraint function over a continuous space.
method Rectified Pessimistic-Optimistic Learning (RPOL) framework, incorporating optimistic and pessimistic GP bandit learning.
result RPOL achieves sublinear regret and minimal cumulative constraint violation.
Develops methods for dynamic pricing in incomplete data settings.
problem Incomplete historical data makes optimal pricing difficult.
method Nonparametric partial identification framework for offline dynamic pricing.
result Pessimistic and opportunistic policies with regret bounds.
Semi-pessimistic RL tackles distributional shift and data scarcity in offline RL.
problem Distributional shift and scarcity of labeled data in offline RL.
method Proposes a semi-pessimistic RL method that simplifies learning by seeking a lower bound of the reward function.
result Demonstrates clear competitiveness and improved policy learning with vast unlabeled data.
Study online learning with off-policy feedback in adversarial bandit problems.
problem Learning with limited direct feedback in sequential decision making.
method Proposed algorithms that adapt pessimistic reward estimators to handle unknown behavior policy.
result Guaranteed regret bounds scaling with policy mismatch, improving performance against well-covered comparators.
PESCAL uses mediators to learn from confounded offline data.
problem Learning from confounded observational data in reinforcement learning.
method PESCAL uses mediator variables and the pessimistic principle to address confounding bias and distributional shift.
result It is sufficient to learn a lower bound of the mediator distribution function to mitigate distributional shift.
The paper introduces Bellman-consistent pessimism to improve offline reinforcement learning without overly pessimistic bias.
problem Offline reinforcement learning's challenge of discovering good policies without exhaustive exploration.
method Introduces Bellman-consistent pessimism for function approximation, improving sample complexity and adaptability.
result Improves sample complexity by O ( d ) \mathcal{O}(d) O ( d ) in the action space finite case, and automatically adapts to bias-variance tradeoff. POLAR optimizes treatment strategies in dynamic settings with statistical guarantees.
problem Optimizing sequential decisions in dynamic treatment regimes with robustness and statistical guarantees.
method Pessimistic model-based approach estimating transition dynamics and incorporating uncertainty penalties.
result Offers statistical and computational guarantees, including finite-sample bounds on policy suboptimality.
Pessimistic model-based algorithm finds Nash equilibria in zero-sum Markov games from offline data.
problem Learning Nash equilibria in two-player zero-sum Markov games from limited data.
method Pessimistic model-based algorithm with Bernstein-style lower confidence bounds (VI-LCB-Game).
result Proves sample complexity no larger than C c l i p p e d ⋆ S ( A + B ) ( 1 − γ ) 3 ε 2 \frac{C_{\mathsf{clipped}}^\star S(A+B)}{(1-γ)^3 \varepsilon^2} ( 1 − γ ) 3 ε 2 C clipped ⋆ S ( A + B ) , achieving minimax optimality. This paper develops a model of reference-dependent assessment of subjective beliefs in which loss-averse people optimally choose the expectation as the reference point to balance the current felicity from the optimistic anticipation and the future disappointment from the realisation. The choice of over-optimism or over…
In the presence of model risk, it is well-established to replace classical expected values by worst-case expectations over all models within a fixed radius from a given reference model. This is the "robustness" approach. We show that previous methods for measuring this radius, e.g. relative entropy or polynomial diverg…
Actor-critic methods, a type of model-free Reinforcement Learning, have been successfully applied to challenging tasks in continuous control, often achieving state-of-the art performance. However, wide-scale adoption of these methods in real-world domains is made difficult by their poor sample efficiency. We address th…
Value iteration is a fixed point iteration technique utilized to obtain the optimal value function and policy in a discounted reward Markov Decision Process (MDP). Here, a contraction operator is constructed and applied repeatedly to arrive at the optimal solution. Value iteration is a first order method and therefore …
Paper develops neural network approximation for pessimistic offline RL with theoretical guarantees.
problem Challenges in offline reinforcement learning with deep neural networks and data dependence.
method Establishes estimation error for pessimistic offline RL using neural network approximation with C \mathcal{C} C -mixing data. result Explicit efficiency of deep adversarial offline RL frameworks demonstrated with two converging error components.
PASTA optimizes assortment selection using pessimism principle.
problem Optimizing assortment selection with limited data coverage.
method Pessimistic Assortment Optimization (PASTA) based on the principle of pessimism.
result PASTA correctly identifies optimal assortment with minimal data coverage.
New algorithm reduces offline RL sample complexity for MDPs.
problem Learning optimal policies from offline data in unknown MDPs.
method Adaptive Pessimistic Value Iteration (APVI) algorithm.
result Suboptimality bound nearly matches theoretical limits.
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 …
New RL algorithms find SNE in Markov games with myopic followers.
problem Finding SNE in Markov games with myopic followers.
method Optimistic and pessimistic variants of least-squares value iteration, incorporating function approximation.
result First provably efficient RL algorithms for SNEs in general-sum Markov games with myopic followers.
Softmax PG methods can take extremely long to converge, even with exact gradients.
problem Softmax policy gradient methods can take an impractically long time to converge in reinforcement learning.
method Softmax policy gradient methods with exact gradient computation.
result Softmax PG methods can take exponential number of iterations to converge, even with optimal initialization.
Graph neural network executes value iteration for flexible environments.
problem Value iteration in flexible environments with direct supervision.
method Graph Neural Network (GNN) executing value iteration algorithm.
result GNN accurately models value iteration across diverse environments.
Study optimal product assortment using historical data, proving item coverage suffices.
problem Offline assortment optimization under MNL model with limited historical data.
method Pessimistic Rank-Breaking (PRB) algorithm combining rank-breaking and pessimistic estimation.
result Optimal item coverage is both sufficient and necessary for efficient offline learning.
Agent maximizes utility with pathwise constraint on portfolio value.
problem Maximizing utility with a pathwise constraint on portfolio value.
method Max-plus decomposition for supermartingales, Black-Scholes-Merton model.
result Explicit form of optimal terminal wealth and process involved.
This study tackles adversarial corruption in model-based reinforcement learning.
problem Adversarial corruption in model-based reinforcement learning.
method Maximum likelihood estimation (MLE) approach for learning transition model in both online and offline settings.
result Proves a regret of i l d e O ( T + C ) ilde{\mathcal{O}}(\sqrt{T} + C) i l d e O ( T + C ) for CR-OMLE and a suboptimality of O ( C / n ) \mathcal{O}(C/n) O ( C / n ) for CR-PMLE. I study the behavior and the performance of the long-term forecasts issued by financial analysts with respect to the Extrapolation Hypothesis. That hypothesis states that investors, extrapolating from the firms' recent performances, are too optimistic about growth and large firms and too pessimistic about value and sma…
This paper analyzes multi-pass SGD for least squares, improving generalization bounds.
problem Improving generalization bounds for multi-pass SGD in the least squares problem.
method Develops an instance-dependent excess risk bound for least squares in the interpolation regime.
result SGD performs worse than GD instance-wise but saves computational time.
XLVINs improve data efficiency in implicit planning by leveraging latent space.
problem Improving data efficiency in implicit planning algorithms.
method XLVINs use a high-dimensional latent space to perform planning computations, breaking the algorithmic bottleneck.
result XLVINs significantly improve data efficiency across various settings compared to value iteration-based implicit planners and model-free baselines.
MOReL learns offline RL policies using pessimistic MDPs.
problem Offline RL's data efficiency and velocity.
method Two-step process: learn P-MDP and near-optimal policy in it.
result MOReL is minimax optimal and matches state-of-the-art results.