Nonlinear Multi-objective Reinforcement Learning with Provable
Guarantees
- URL: http://arxiv.org/abs/2311.02544v2
- Date: Thu, 14 Dec 2023 20:33:01 GMT
- Title: Nonlinear Multi-objective Reinforcement Learning with Provable
Guarantees
- Authors: Nianli Peng and Brandon Fain
- Abstract summary: RA-E3 is an algorithm with provable guarantees for solving a single or multi-objective Decision Process (MDP)
RA-E3 extends the classic E3 algorithm that solves MDPs with scalar rewards and linear preferences.
- Score: 1.6160052850279416
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We describe RA-E3 (Reward-Aware Explicit Explore or Exploit), an algorithm
with provable guarantees for solving a single or multi-objective Markov
Decision Process (MDP) where we want to maximize the expected value of a
nonlinear function over accumulated rewards. This allows us to model
fairness-aware welfare optimization for multi-objective reinforcement learning
as well as risk-aware reinforcement learning with nonlinear Von
Neumann-Morgenstern utility functions in the single objective setting. RA-E3
extends the classic E3 algorithm that solves MDPs with scalar rewards and
linear preferences. We first state a distinct reward-aware version of value
iteration that calculates a non-stationary policy that is approximately optimal
for a given model of the environment. This sub-procedure is based on an
extended form of Bellman optimality for nonlinear optimization that explicitly
considers time and current accumulated reward. We then describe how to use this
optimization procedure in a larger algorithm that must simultaneously learn a
model of the environment. The algorithm learns an approximately optimal policy
in time that depends polynomially on the MDP size, desired approximation, and
smoothness of the nonlinear function, and exponentially on the number of
objectives.
Related papers
- Computationally Efficient RL under Linear Bellman Completeness for Deterministic Dynamics [39.07258580928359]
We study computationally and statistically efficient Reinforcement Learning algorithms for the linear Bellman Complete setting.
This setting uses linear function approximation to capture value functions and unifies existing models like linear Markov Decision Processes (MDP) and Linear Quadratic Regulators (LQR)
Our work provides a computationally efficient algorithm for the linear Bellman complete setting that works for MDPs with large action spaces, random initial states, and random rewards but relies on the underlying dynamics to be deterministic.
arXiv Detail & Related papers (2024-06-17T17:52:38Z) - Two-Stage ML-Guided Decision Rules for Sequential Decision Making under Uncertainty [55.06411438416805]
Sequential Decision Making under Uncertainty (SDMU) is ubiquitous in many domains such as energy, finance, and supply chains.
Some SDMU are naturally modeled as Multistage Problems (MSPs) but the resulting optimizations are notoriously challenging from a computational standpoint.
This paper introduces a novel approach Two-Stage General Decision Rules (TS-GDR) to generalize the policy space beyond linear functions.
The effectiveness of TS-GDR is demonstrated through an instantiation using Deep Recurrent Neural Networks named Two-Stage Deep Decision Rules (TS-LDR)
arXiv Detail & Related papers (2024-05-23T18:19:47Z) - Pessimistic Nonlinear Least-Squares Value Iteration for Offline
Reinforcement Learning [58.962016644796]
We propose an oracle-efficient algorithm, dubbed Pessimistic Least-Square Value Iteration (PNLSVI) for offline RL with non-linear function approximation.
Our algorithm enjoys a regret bound that has a tight dependency on the function class complexity and achieves minimax optimal instance-dependent regret when specialized to linear function approximation.
arXiv Detail & Related papers (2023-10-02T17:42:01Z) - Regularization and Variance-Weighted Regression Achieves Minimax
Optimality in Linear MDPs: Theory and Practice [79.48432795639403]
Mirror descent value iteration (MDVI) is an abstraction of Kullback-Leibler (KL) and entropy-regularized reinforcement learning (RL)
We study MDVI with linear function approximation through its sample complexity required to identify an $varepsilon$-optimal policy.
We present Variance-Weighted Least-Squares MDVI, the first theoretical algorithm that achieves nearly minimax optimal sample complexity for infinite-horizon linear MDPs.
arXiv Detail & Related papers (2023-05-22T16:13:05Z) - Sample Efficient Model-free Reinforcement Learning from LTL
Specifications with Optimality Guarantees [17.69385864791265]
We present a model-free Reinforcement Learning (RL) approach that efficiently learns an optimal policy for an unknown system.
We also provide improved theoretical results on choosing the key parameters to ensure optimality.
arXiv Detail & Related papers (2023-05-02T12:57:05Z) - Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision
Processes [80.89852729380425]
We propose the first computationally efficient algorithm that achieves the nearly minimax optimal regret $tilde O(dsqrtH3K)$.
Our work provides a complete answer to optimal RL with linear MDPs, and the developed algorithm and theoretical tools may be of independent interest.
arXiv Detail & Related papers (2022-12-12T18:58:59Z) - Maximum-Likelihood Inverse Reinforcement Learning with Finite-Time
Guarantees [56.848265937921354]
Inverse reinforcement learning (IRL) aims to recover the reward function and the associated optimal policy.
Many algorithms for IRL have an inherently nested structure.
We develop a novel single-loop algorithm for IRL that does not compromise reward estimation accuracy.
arXiv Detail & Related papers (2022-10-04T17:13:45Z) - Sparse Bayesian Learning via Stepwise Regression [1.2691047660244335]
We propose a coordinate ascent algorithm for SBL termed Relevance Matching Pursuit (RMP)
As its noise variance parameter goes to zero, RMP exhibits a surprising connection to Stepwise Regression.
We derive novel guarantees for Stepwise Regression algorithms, which also shed light on RMP.
arXiv Detail & Related papers (2021-06-11T00:20:27Z) - Provable Multi-Objective Reinforcement Learning with Generative Models [98.19879408649848]
We study the problem of single policy MORL, which learns an optimal policy given the preference of objectives.
Existing methods require strong assumptions such as exact knowledge of the multi-objective decision process.
We propose a new algorithm called model-based envelop value (EVI) which generalizes the enveloped multi-objective $Q$-learning algorithm.
arXiv Detail & Related papers (2020-11-19T22:35:31Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.