Reinforcement Learning via Fenchel-Rockafellar Duality

By Ofir Nachum, Bo Dai. 2020

137 citations recorded by the source corpus.

We review basic concepts of convex duality, focusing on the very general and supremely useful Fenchel-Rockafellar duality. We summarize how this duality may be applied to a variety of reinforcement learning (RL) settings, including policy evaluation or optimization, online or offline learning, and discounted or undiscounted rewards. The derivations yield a number of intriguing results, including the ability to perform policy evaluation and on-policy policy gradient with behavior-agnostic offline data and methods to learn a policy via max-likelihood optimization. Although many of these results have appeared previously in various forms, we provide a unified treatment and perspective on these results, which we hope will enable researchers to better use and apply the tools of convex duality to make further progress in RL.

Subfields: Artificial Intelligence, Cognitive Neuroscience, Reinforcement Learning, Mathematical Optimization

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Cognitive Neuroscience

In Reinforcement Learning

In Mathematical Optimization

Citations in the corpus

Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problems (2020, positive): “Nachum et al. (2019b); Nachum and Dai (2020) build on a similar framework to devise an off-policy RL algorithm.”
MOReL : Model-Based Offline Reinforcement Learning (2020, methodology): “Finally, a recent line of work [22, 54] focuses on obtaining provably convergent methods for minimizing the (one-step) Bellman error using Duality theory.”
Statistical Bootstrapping for Uncertainty Estimation in Off-Policy Evaluation (2020, methodology): “For the next assumption, we make use of the discounted on-policy distribution d, which measures the likelihood of the policy π encountering state-action pair (s, a) when interacting withM [24]:”
VIP: Towards Universal Visual Reward and Representation via Value-Implicit Pre-Training (2022, background): “Our work is also closely related to Ma et al. (2022b), which ﬁrst introduced the dual ofﬂine GCRL objective based on Fenchel duality (Rockafellar, 1970; Nachum & Dai, 2020; Ma et al., 2022a).”
Offline Policy Selection under Uncertainty (2020, methodology): “We further re-frame the constraint with Fenchel duality [Nachum and Dai, 2020]”
Experience Replay with Likelihood-free Importance Weights (2020, background): “Dual representations of f -divergences are also leveraged in reinforcement learning (Nachum et al., 2019; Nachum and Dai, 2020), but it is used over a regularizer that encourages exploration to be closer to off-policy experiences; the importance weights are added to the reward function when computin”
Is Pessimism Provably Efficient for Offline RL? (2020, background): “…et al., 2018; Xie et al., 2019; Nachum et al., 2019a;b; Tang et al., 2019; Kallus and Uehara, 2019; 2020; Jiang and Huang, 2020; Uehara et al., 2020; Duan et al., 2020; Yin and Wang, 2020; Yin et al., 2020; Nachum and Dai, 2020; Yang et al., 2020a; Zhang et al., 2020b) and the references therein.”
Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism (2021, background): “Based on this intuition, a variety of model-based [55, 19, 56] and model-free [22, 33, 11, 34, 25, 37, 44, 14, 28, 23, 3] offline RL algorithms are proposed that achieve promising empirical results.”
Minimax Confidence Interval for Off-Policy Evaluation and Policy Optimization (2020, methodology): “Our derivation uses Fenchel-Legendre transformation in a way similar to [18, 19]: we assume that f : R → R has a convex conjugate f∗ (i.”
A Review of Safe Reinforcement Learning: Methods, Theory and Applications (2022, methodology): “[222] propose the DCRL method that is to optimise the reward and cost from the perspective of an optimisation criterion based on optimisation theory, in which they consider the safety constraints via the duality property [65, 196, 197, 268] with regard to the state density functions, rather than the”