Achieving Sub-linear Regret in Infinite Horizon Average Reward Constrained MDP with Linear Function Approximation

Arnob Ghosh, Xingyu Zhou, Ness ShroffICLR 2023 · OpenReview

Introduction

While reinforcement learning (RL) has seen massive success, theoretical guarantees often focus on episodic settings (where tasks have clear beginnings and ends) or unconstrained environments (where the sole objective is maximizing reward). However, real-world applications—such as autonomous driving or data center management—operate on an infinite horizon and must strictly adhere to safety or resource constraints. Furthermore, continuous or massive state spaces render traditional tabular methods intractable, necessitating function approximation.

This paper introduces the first model-free RL algorithms for infinite-horizon average reward Constrained Markov Decision Processes (CMDPs) using linear function approximation. By assuming the environment's dynamics can be represented as linear combinations of known features, the authors bridge a critical gap in the literature, offering algorithms that balance computational efficiency, theoretical regret bounds, and environmental assumptions.

Methodology

The authors propose three distinct algorithms to navigate the complexities of infinite-horizon CMDPs:

  1. Algorithm 1 (Fixed-Point Optimization): A model-free approach leveraging "optimism under uncertainty." It searches for a policy within a smooth soft-max policy class. This smoothness is critical for proving uniform concentration bounds in large state spaces, though the algorithm remains computationally inefficient.
  2. Algorithm 2 (Episodic Primal-Dual): To achieve computational efficiency, this method divides the infinite timeline into episodes of length $H$. It applies a primal-dual adaptation of the Least-Squares Value Iteration (LSVI-UCB) algorithm, allowing periodic policy updates rather than solving complex optimizations at every step.
  3. Algorithm 3 (Policy-Based MDP-EXP2): A primal-dual adaptation of the classic EXP2 multi-armed bandit algorithm. It updates the policy via Online Mirror Descent. This lightweight approach can achieve zero constraint violation under stricter ergodicity assumptions (i.e., the agent eventually visits all parts of the state space regardless of its starting point).

Key Insights

Several novel theoretical insights enable these algorithms to function effectively in the infinite-horizon constrained setting:

  • The "Smoothness" Requirement: Unlike unconstrained RL where greedy policies often suffice, constrained RL with function approximation requires smooth policies (like a soft-max policy) to ensure value functions are well-behaved enough to guarantee convergence to the optimum.
  • Bridging Infinite and Finite Horizons: Algorithm 2's episodic chunking balances the bias introduced by cutting the timeline against the variance of learning. By carefully tuning the episode length $H$ as a function of total time $T$, the infinite horizon becomes manageable.
  • Achieving Zero Violation: Most constrained RL algorithms settle for "sub-linear" violation, meaning mistakes grow slower than time but still accumulate. The authors demonstrate that by optimizing for a tighter constraint than strictly required (being conservative), the agent can eventually reach a state of absolute zero constraint violation.

Theoretical Results

The paper evaluates performance via Regret (lost reward compared to the optimal policy) and Constraint Violation (the degree to which the agent exceeded safety limits).

  • Algorithm 1: Achieves $\tilde{\mathcal{O}}(\sqrt{d^3T})$ regret and violation. While nearly optimal in time $T$, it is computationally expensive.
  • Algorithm 2: Achieves $\tilde{\mathcal{O}}((dT)^{3/4})$ regret and violation. It is computationally efficient and improves upon previous state-of-the-art bounds for tabular settings (which were $\tilde{\mathcal{O}}(T^{5/6})$) under weaker assumptions.
  • Algorithm 3: Achieves $\tilde{\mathcal{O}}(\sqrt{T})$ regret and violation under ergodicity assumptions. Crucially, it can achieve zero constraint violation for sufficiently large $T$.

Empirical Evaluation

Though primarily theoretical, the authors validate Algorithm 3 on a synthetic wireless node transmission environment. The node manages a packet queue, choosing transmission power to maximize reward (inversely related to power) while keeping the average queue length below a threshold. This serves as a practical proof-of-concept for the sub-linear growth of regret and constraint violation.

Limitations and Future Directions

While this work establishes foundational bounds for linear CMDPs, several challenges remain:

  • Computational Efficiency vs. Optimality: Algorithm 1 offers the best theoretical bounds under general assumptions but remains computationally inefficient due to complex fixed-point optimizations.
  • The Linearity Assumption: The reliance on a "Linear MDP" assumption is a limitation. Real-world dynamics are often highly non-linear, and extending these proofs to non-linear function approximation (e.g., deep neural networks) remains a major open challenge.
  • Hyperparameter Knowledge: The algorithms require prior knowledge of environmental constants like the mixing time ($t_{mix}$) or the Slater constant ($\gamma$). Developing fully parameter-free variants would significantly enhance their robustness in unknown environments.

Summary updated

Abstract

We study the infinite horizon average reward constrained Markov Decision Process (CMDP). In contrast to existing works on model-based, finite state space, we consider the model-free linear CMDP setup. We first propose a computationally inefficient algorithm and show that $\tilde{\mathcal{O}}(\sqrt{d^3T})$ regret and constraint violation can be achieved, in which $T$ is the number of interactions, and $d$ is the dimension of the feature mapping. We also propose an efficient variant based on the primal-dual adaptation of the LSVI-UCB algorithm and show that $\tilde{\mathcal{O}}((dT)^{3/4})$ regret and constraint violation can be achieved. This improves the known regret bound of $\tilde{\mathcal{O}}(T^{5/6})$ for the finite state-space model-free constrained RL which was obtained under a stronger assumption compared to ours. We also develop an efficient policy-based algorithm via novel adaptation of the MDP-EXP2 algorithm to our primal-dual set up with $\tilde{\mathcal{O}}(\sqrt{T})$ regret and even zero constraint violation bound under a stronger set of assumptions.
BibTeX
@inproceedings{ghosh2023achieving,
  author = {Arnob Ghosh and Xingyu Zhou and Ness Shroff},
  title = {{Achieving Sub-linear Regret in Infinite Horizon Average Reward Constrained MDP with Linear Function Approximation}},
  booktitle = {International Conference on Learning Representations},
  year = {2023},
  url = {https://openreview.net/forum?id=zZhX4eYNeeh},
}
Figure