Technical Summary: Primal-Dual Policy Optimization for Linear CMDPs with Adversarial Losses

Problem Setting

This paper addresses the challenge of Safe Reinforcement Learning (RL) in environments where safety constraints must be satisfied despite adversarial perturbations. Specifically, the authors consider Finite-Horizon Adversarial Linear Constrained Markov Decision Processes (CMDPs).

The setting is defined by the tuple $\mathcal{M} = (H, \mathcal{S}, \mathcal{A}, \{P_h\}, \{f^k\}, \{g^k\}, s_1, b)$, where:

• Adversarial Losses: The loss functions $f^k = \{f^k_h\}$ are chosen arbitrarily by an adversary at the beginning of each episode $k$ (full-information feedback). These losses are not drawn from a fixed distribution.
• Stochastic Costs: The cost functions $g^k = \{g^k_h\}$ are sampled i.i.d. from a fixed distribution $G$ (bandit feedback), representing safety constraints.
• Linear Structure: The transition kernels, loss functions, and cost functions possess a linear structure with respect to a known feature mapping $\phi: \mathcal{S} \times \mathcal{A} \to \mathbb{R}^d$.
• Objective: The agent seeks a policy that minimizes cumulative expected loss while ensuring the expected cumulative cost does not exceed a budget $b$.

The performance is measured by Regret (cumulative loss difference compared to the optimal policy) and Constraint Violation (cumulative excess cost over the budget). The goal is to achieve sublinear bounds for both metrics.

Methodology

The authors propose a Primal-Dual Policy Optimization algorithm (Algorithm 1) designed to handle the interplay between adversarial losses and stochastic constraints in a linear function approximation setting. The algorithm integrates four main components:

1. Epoch Initialization and Feature Contraction:
   The algorithm operates in epochs. An epoch begins when the determinant of the design matrix $\Lambda^k_h$ increases by a multiplicative factor. Upon initialization, the policy is reset to a uniform policy, and the dual variable is reset to zero. Crucially, the algorithm employs feature contraction, shrinking the original feature $\phi$ using a sigmoid function to prevent Q-function estimates from expanding uncontrollably. This technique, adapted from Cassel & Rosenberg (2024), simplifies the policy representation for covering number arguments.

2. Policy Execution and Estimation:
   In each episode, the agent executes actions based on the current policy, observes the adversarial loss and stochastic cost, and updates the design matrix. It then estimates the parameters for the loss and cost functions and computes Q-function estimates ($\hat{Q}$) and value function estimates ($\hat{V}$) using the contracted features and optimistic bonuses.

3. Periodic Policy Mixing:
   A core innovation is periodic policy mixing. Instead of mixing the policy (perturbing it towards a uniform policy) in every episode, the algorithm applies mixing only once every $K^B$ episodes (where $B=3/4$).

   • Motivation: Frequent mixing is necessary to bound the dual variable (via drift analysis) but increases the complexity of the policy class (covering number). Periodic mixing balances these competing requirements.
   • Mechanism: Every $K^{3/4}$ episodes, the current policy $\hat{\pi}^k$ is mixed with the uniform policy $\pi_{unif}$ via a convex combination: $\tilde{\pi}^k = (1-\theta)\hat{\pi}^k + \theta\pi_{unif}$.

4. Regularized Dual Update:
   The dual variable $Y^k$ (associated with the cost constraint) is updated using a regularized gradient ascent step:
   $$Y^{k+1} \leftarrow \left[ (1 - 4\alpha\eta H^3)Y^k + \eta(\hat{V}^k_{g,1}(s_1) - b - 4\alpha H^3 - 4\theta H^2) \right]_+$$
   The regularization terms ($-4\alpha\eta H^3 Y^k$ and constants) are designed to pull the dual variable toward zero, enabling a Lyapunov drift analysis to bound $Y^k$ without relying on the strong duality assumptions that fail in adversarial settings.

5. Weighted LogSumExp Softmax Policies:
   The resulting policy class is a weighted LogSumExp softmax. Due to the periodic mixing, the policy is not a simple exponential of the sum of Q-functions but a weighted sum of exponentials of partial sums of Q-function estimates. This structure allows the policy to adapt to adversarially chosen losses while maintaining a tractable covering number.

Key Contributions

1. First Sublinear Bounds for Adversarial Linear CMDPs:
   The paper presents the first algorithm to achieve sublinear regret and constraint violation bounds in the setting of linear CMDPs with adversarial losses and stochastic costs. The bounds are $\tilde{O}(K^{3/4})$, where $K$ is the number of episodes.

2. New Covering Number Argument:
   The authors establish a novel covering number argument for the weighted LogSumExp softmax policies. Unlike standard softmax policies where weights are uniform, the mixing process introduces varying weight parameters $\zeta_i$. The authors prove that the logarithm of the covering number for this class grows as $\tilde{O}(n^2 d^2)$, where $n$ is the number of mixing steps and $d$ is the feature dimension. This result is non-trivial because the weight parameters depend on both the mixing parameter and Q-function estimates.

3. Algorithmic Components for Control:
   The paper introduces two novel components to jointly control the covering number and the dual variable:

   • Periodic Policy Mixing: Regulates the frequency of mixing to prevent the covering number from growing too large (which would happen with $O(K)$ mixing steps) while still occurring frequently enough to bound the dual variable.
   • Regularized Dual Update: A new update rule that incorporates a regularization term to facilitate drift-based analysis, allowing for the bounding of the dual variable in the absence of strong duality.

Results

Theoretical Guarantees:
Under the Slater condition (Assumption 1) and assuming $H^2 \leq K$, with probability at least $1-\delta$, the algorithm achieves:

• Regret: $\tilde{O}\left(\sqrt{d^3}H^4 K^{3/4} + dH^3 K^{3/4} + d^3 H^4 K^{1/2} + \frac{H^6}{\gamma^2} K^{1/4} + \frac{dH^6}{\gamma^2}\right)$
• Constraint Violation: $\tilde{O}\left(\frac{dH^5}{\gamma} K^{3/4} + \sqrt{d^3}H^4 K^{3/4} + d^3 H^4 K^{1/2}\right)$

Both metrics scale sublinearly with $K$ (specifically $K^{3/4}$), indicating that the average regret and average constraint violation converge to zero as the number of episodes increases.

Numerical Experiments:
The algorithm was evaluated on a modified job-scheduling CMDP with adversarial losses. Over $100,000$ episodes:

• Regret: Grew sublinearly, confirming the theoretical bound.
• Constraint Violation: Initially grew rapidly but converged to zero after approximately 45,000 episodes, validating the algorithm's ability to satisfy safety constraints in the long run.

Significance and Claims

The paper claims to be the first provably efficient algorithm for safe RL with linear function approximation in adversarial settings. Its significance lies in bridging the gap between:

1. Tabular Adversarial CMDPs: Previous works (e.g., Qiu et al., 2020) handled adversarial settings but were limited to small, finite state spaces.
2. Linear Stochastic CMDPs: Previous works (e.g., Ghosh et al., 2022) handled large state spaces but assumed stationary (stochastic) environments.

By introducing the weighted LogSumExp softmax policy and the periodic mixing strategy, the authors demonstrate that it is possible to handle large state spaces (via linear approximation) and adversarial losses simultaneously. The paper modestly notes that while $\tilde{O}(K^{3/4})$ is achieved, the optimal $\tilde{O}(\sqrt{K})$ bound remains an open question for this specific setting, particularly regarding the trade-off between mixing steps and covering numbers. The work also highlights the difficulty of extending occupancy-measure-based dual updates to policy-based methods in adversarial linear CMDPs, justifying the proposed primal-dual policy optimization approach.