Source-linked AI summary
Reinforcement Learning via Fenchel-Rockafellar Duality
Ofir Nachum, Bo Dai
TL;DR
RL requires learning policies from sampled experience in sequential environments whose dynamics are unknown. This paper develops a unified convex-duality treatment of RL formulations, including policy evaluation and optimization across online or offline and discounted or undiscounted settings. Its derivations include policy gradients from offline data and policy evaluation solutions that remain unchanged when the dual objective changes.
Problem
RL involves sequential decisions with long-term effects, while learners know the environment only through sampled trajectories and do not know its underlying dynamics.
Source: §1 · p. 1Method
The paper generalizes LP formulations to convex objectives and linear constraints, applying Fenchel-Rockafellar duality and related dualities to RL problems.
Source: §1 · p. 2Results
Danskin’s theorem supports on-policy policy gradients from offline data, and changing the dual Q-LP objective does not change its solution dπ.
Source: §4.4 · p. 15, §5.5 · p. 18Takeaways & Limitations
The paper presents a unified duality-based protocol for policy evaluation, policy optimization, and imitation learning across online or offline access and discounted or undiscounted rewards.
Source: §8 · p. 24The Q-value Lagrangian estimator involves environment rewards and can be difficult to optimize from single-step transitions; its bilinear Lagrangian can also cause instability or poor convergence.
Source: §4.2 · p. 12
Abstract
from arXiv · showhide
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.
1 Introduction
RL combines sequential decisions with knowledge limited to sampled experience, while dynamic-programming methods can be unstable in some settings. The paper presents convex duality as a broader framework for formulating and solving RL problems.
1 Introduction
- RL poses sequential decision problems in which early choices affect later outcomes, while the learner observes sampled trajectories without knowing the environment dynamics.The paper notes applications including robotics, patient care, and recommendation systems.Source: §1 · p. 1
- Temporal-difference methods approximate Bellman fixed points, but training can oscillate or diverge with function approximation or limited access to further interactions.The paper situates LP and convex-optimization approaches as alternatives to dynamic-programming methods.Source: §1 · pp. 1–2
- Fenchel-Rockafellar duality generalizes the LP approach to convex objectives with linear constraints and yields unconstrained duals when the primal objective is strictly convex.The paper presents this as a useful property distinguishing the generalization from the LP setting.Source: §1 · p. 2
- The paper presents duality-based reformulations for policy evaluation, policy optimization, and imitation learning across online or offline access and discounted or undiscounted rewards.Its derivations build on a unified perspective intended to help researchers apply convex duality in RL.Source: §1 · p. 2
2 Convex Duality
The section reviews convex duality tools used in later RL derivations, from Fenchel conjugates and f-divergences to Fenchel-Rockafellar, Lagrangian, and LP duality. It notes that the mathematical treatment is informal and not a full introduction to convex analysis.
2 Convex Duality
- Duality can reformulate optimization problems in alternative forms that may be more tractable, and the section reviews results used in later RL algorithms.The treatment is intentionally informal rather than a full introduction to convex analysis.Source: §2 · p. 3
2.1 Fenchel Conjugate
- For convex functions, the Fenchel conjugate is also called the convex conjugate or Legendre–Fenchel transformation; the section assumes convex functions are proper and lower semi-continuous.It states that the conjugate of a proper, convex, lower semi-continuous function has those properties and that f** = f.Source: §2.1 · p. 3
2.1.1 The Indicator Function
- The indicator function can express constraints, and Table 1 lists common functions alongside their Fenchel conjugates.For example, an equality constraint Ax = 0 can be represented by adding the indicator of {0} applied to Ax.Source: §2.1.1 · p. 4, Table 1 · p. 4
2.1.2 f-Divergences
- f-divergences measure discrepancy between distributions, and their conjugates depend on whether the domain is unrestricted real-valued functions or distributions.For KL divergence, the constrained conjugate is a log-average-exp function.Source: §2.1.2 · pp. 4–5
2.2 Fenchel-Rockafellar Duality
- Fenchel-Rockafellar duality relates a convex optimization problem to a dual formed using convex conjugates and a linear operator.The section gives the dual under mild conditions and describes recovery of primal solutions from dual solutions.Source: §2.2 · pp. 5–6
2.2.1 The Lagrangian
- Fenchel-Rockafellar duality yields Lagrangian duality, whose optimal value matches the original problem’s value and whose equilibrium points solve the primal and dual.The derivation expresses a constrained problem using an indicator function and the Lagrangian.Source: §2.2.1 · pp. 6–7
2.2.2 LP Duality
- Fenchel-Rockafellar duality generalizes LP duality: when the primal LP is feasible, its result equals the dual’s.The section obtains the familiar LP form by choosing a linear objective with nonnegativity constraints and an indicator for the equality constraint.Source: §2.2.2 · p. 7
3 Reinforcement Learning
This section introduces RL as sequential decision-making through an MDP and distinguishes evaluating a policy from finding an optimal one. It also defines the offline setting and the Q-values and state-action visitations used to express these problems.
3 Reinforcement Learning
- RL studies policies that make sequential decisions from sampled experience, with rewards and stochastic state transitions shaping long-term outcomes.The paper frames its later applications of Fenchel-Rockafellar, LP, and Lagrangian duality in this setting.Source: §3 · p. 7
3.1 Markov Decision Process
- An MDP specifies states, actions, rewards, transitions, an initial-state distribution, and a discount factor; policy decisions induce rewards and subsequent state transitions.The section assumes infinite-horizon environments, with finite horizons representable using a zero-reward terminal state that loops to itself.Source: §3.1 · pp. 7–8
3.2 Policy Evaluation and Optimization
- Policy evaluation estimates a given policy’s long-term discounted reward, while policy optimization seeks a policy that maximizes that quantity.With policy-independent rewards an optimal deterministic policy exists; policy-dependent regularization can instead yield a stochastic optimum.Source: §3.2 · p. 8
3.3 Online vs. Offline RL
- Offline RL uses a fixed dataset of logged experience rather than new environment interactions, and the paper focuses on an effectively unlimited-data version of this setting.The offline distribution can mismatch the distribution needed for policy evaluation or optimization; finite-sample analysis is outside the report’s scope.Source: §3.3 · p. 9
3.4 Q-values and State-Action Visitations
- Q-values measure future discounted rewards, while state-action visitations measure discounted on-policy encounters; both help express policy value and policy gradients.The section notes that algorithms commonly estimate Q-values and either access or estimate the visitation distribution.Source: §3.4 · pp. 9–10
4 Policy Evaluation
The section develops policy evaluation formulations using LP, Lagrangian, and Fenchel-Rockafellar duality. These formulations connect policy value, Q-values, and state-action visitations, and yield offline estimators with distinct practical properties and limitations.
4.1 The Linear Programming Form of Q
- The Q-LP characterizes policy value through Q-values, and its dual has the policy’s state-action visitation as its solution.The Q-LP solution agrees with Qπ on state-action pairs reachable by the policy; the dual’s equality constraints uniquely determine its visitation solution.Source: §4.1 · p. 11
4.2 Policy Evaluation via the Lagrangian
- The Q-LP Lagrangian yields an offline policy-value estimator that is doubly robust to errors in either Q or the density ratio.Its value equals ρ(π) when either Q or ζ is optimal, and the estimator requires samples from the initial-state distribution, offline data, and policy.Source: §4.2 · pp. 11–12
4.3 Changing the Problem Before Applying Duality
- Because the dual constraints already determine dπ, changing its objective can preserve the solution while making the resulting optimization more tractable.The reformulation is motivated in part by potential instability in the original LP approach.Source: §4.3 · p. 12
4.3.1 Constant Function h(d) := 0
- The f-divergence formulation recovers the general saddle-point form of DualDICE, whose approximate density ratio can estimate policy value.The derivations also connect the Fenchel-Rockafellar dual to the alternative change-of-variables called the DualDICE trick.Source: §4.3.2 · pp. 13–14
- With h(d)=0, the Bellman residuals of an optimized zero-reward Q-function give the density ratio between on-policy and offline state-action distributions.The resulting Fenchel-Rockafellar dual is unconstrained and can use offline-data expectations; its transition-expectation objective can be biased when a single empirical next-state sample stands in for the transition distribution.Source: §4.3.2 · pp. 14–15
4.4 Summary
- The section’s summary emphasizes that a suitable change of objective can yield an unconstrained Fenchel-Rockafellar dual amenable to stochastic and offline settings.It also recaps the Q-LP, its visitation dual, and the doubly robust estimator from the Lagrangian.Source: §4.4 · p. 15
5 Policy Optimization
The section applies policy-evaluation formulations and convex duality to policy optimization, including offline and regularized settings. It derives on-policy policy gradients from offline data and connects regularized objectives to imitation and max-likelihood learning.
5.1 The Policy Gradient Theorem
- Danskin’s theorem applied to the Lagrangian recovers the policy gradient theorem from the optimized value and visitation variables.At the optima, Q matches Qπ on visited state-action pairs and d equals dπ.Source: §5.1 · pp. 15–16
5.2 Offline Policy Gradient via the Lagrangian
- Optimizing the offline Lagrangian over Q and ζ yields the on-policy policy gradient while using offline samples.The offline formulation represents the visitation ratio as ζ(s, a) = dπ(s, a)/dD(s, a).Source: §5.2 · p. 16
5.3 Fenchel-Rockafellar Duality for Regularized Optimization
- Regularizing the max-reward objective with an f-divergence gives an unconstrained Fenchel-Rockafellar dual and preserves the on-policy-gradient property for regularized Q-values.The regularizer changes the optimal policy, while the optimal visitation remains dπ.Source: §5.3 · pp. 16–17, §5.5 · p. 19
5.3.1 Regularization with the KL-Divergence
- KL regularization yields a dual policy objective resembling max-likelihood learning, but the authors state that it is not exactly equivalent.Its Q-value objective also resembles REPS through a log-average-exp form.Source: §5.3.1 · pp. 17–18
5.4 Imitation Learning
- Ignoring rewards in the f-divergence-regularized objective turns offline policy optimization into occupancy-matching imitation learning.The derived offline objectives resemble Primal AlgaeDICE or Fenchel AlgaeDICE without rewards.Source: §5.4 · p. 18
5 Policy Optimization
- Policy optimization can reuse policy-evaluation estimators by placing a maximization over policies around an estimator of ρ(π).The resulting inner solutions can support on-policy policy gradients even when only offline data are available.Source: §5.5 · p. 18
5.5 Summary
- The section’s summary highlights that regularizer choice can yield objectives resembling actor-critic learning or max-likelihood policy learning.Appropriate regularization can also produce an unconstrained dual problem.Source: §5.5 · p. 19
6 RL with the Linear Programming Form of V
The section develops policy optimization from the V-LP, whose visitation formulation uses state-level flow constraints. Its Fenchel-Rockafellar dual can avoid nested optimization, but policy recovery requires an additional step and may be difficult depending on regularization.
6 RL with the Linear Programming Form of V
- The V-LP formulation expresses policy optimization through state-level flow conservation, with optimal visitation d* equal to dπ* and objective value ρ(π*).The constraints conserve probability mass over states rather than state-action pairs.Source: §6 · p. 19
- Unlike the Q-LP approach, the V-LP dual requires a single optimization over V and K, rather than a nested max-min over π and Q.Its solution gives the regularized value function, not the policy itself.Source: §6 · p. 20
- The optimal policy can be recovered from the V-LP dual’s V* and K* solutions by first obtaining the optimal visitation and then applying Bayes’ rule.The recovered visitation is that of an optimal regularized policy.Source: §6 · p. 20
- The V-LP avoids the Q-LP’s nested max-min optimization, but does not directly provide a policy and may make policy recovery difficult in stochastic settings.The difficulty depends on the specific regularization used.Source: §6 · p. 20
6.1 Max-Likelihood Policy Learning
- KL regularization makes the V-LP dual a log-expected-exponential objective and recovers the REPS objective.The KL dual is defined over a non-negative domain, avoiding the need to handle d ≥ 0 as an additional constraint.Source: §6.1 · p. 21
- Under KL regularization, the optimal visitation is the dataset visitation weighted by a softmax of reward plus the value backup minus value.The policy can then be recovered from V* through max-likelihood learning.Source: §6.1 · p. 21
6.2 Policy Evaluation with the V-LP
- For offline policy evaluation with the V-LP, correcting offline actions to on-policy samples requires knowing the data-distribution policy dD(a|s).This contrasts with behavior-agnostic objectives yielded by the Q-LP.Source: §6.2 · pp. 21–22
7 Undiscounted Settings
The paper extends its duality-based policy evaluation and optimization formulations to undiscounted settings. Policy evaluation estimates average per-step reward through a normalized stationary visitation, while policy optimization retains an on-policy-gradient formulation, with regularized Q-values.
7.1 Policy Evaluation
- For γ = 1, policy evaluation concerns average per-step reward and can express it as an expectation under the policy’s stationary distribution when stated conditions hold.For finite state and action spaces, the cited condition is that the MDP be ergodic.Source: §7.1 · p. 22
- The undiscounted evaluation LP adds a normalization constraint so d is a normalized distribution, while retaining the over-constrained structure used for objective modification.The paper describes a Fenchel-Rockafellar dual after modifying the objective with an f-divergence regularizer.Source: §7.1 · pp. 22–23
7.1.1 Regularized Lagrangian
- A regularized Lagrangian approach corresponding to GenDICE uses χ²-divergence, and its Q and λ regularizers do not change the optimal dual variable.The resulting solution can still estimate policy value.Source: §7.1.1 · p. 23
7.2 Policy Optimization
- In undiscounted policy optimization, Danskin’s theorem gives an on-policy policy gradient with respect to regularized Q-values.The section also presents a KL-regularized V-LP dual and a max-likelihood optimization for recovering the optimal policy.Source: §7.2 · pp. 23–24
8 Conclusion
The conclusion distills a recurring convex-optimization protocol for deriving RL algorithms across learning settings, and identifies extensions and optimization questions for future work.
8 Conclusion
- For difficult problems, formulate constrained convex optimization and solve its Fenchel-Rockafellar dual or Lagrangian form.Source: §8 · p. 24
- When the dual remains difficult, such as when a linear primal objective yields a constrained dual, modify the primal objective with an appropriate convex regularizer.Source: §8 · p. 24
- The protocol yields algorithms for policy evaluation, policy optimization, and imitation learning across online or offline access and discounted or undiscounted rewards.The conclusion presents this breadth as the outcome of a recurring derivation approach.Source: §8 · p. 24
- The authors identify multi-agent, safe, and exploration RL as promising extensions of this protocol.They hope the connections between RL and optimization can spur progress.Source: §8 · p. 24
- Open questions include how the formulations interact with stochastic and function-approximation optimization algorithms and whether they are more efficient than dynamic-programming approaches.Source: §8 · pp. 24–25