Policy performance bound by average divergence

Let a finite discounted CMDP, a bounded transition signal $g$, a bounded function $f:S\to \mathbb{R}$, and stationary policies $\pi ,{\pi }^{\mathrm{\prime }}$ be given. For each state define

${\bar{\delta }}_f^{g,\sigma }(s):={\sum }_{a\in A(s)}{\sum }_{\rho \in \mathcal{R}}{\sum }_{s^{\mathrm{\prime }}\in S}\sigma (a\mid s)p(s^{\mathrm{\prime }},\rho \mid s,a)(g(s,a,\rho ,s^{\mathrm{\prime }})+\gamma f(s^{\mathrm{\prime }})-f(s)),\sigma \in \{\pi ,{\pi }^{\mathrm{\prime }}\}\mathrm{.}$

Set ${ϵ}_f^g({\pi }^{\mathrm{\prime }}):={\max }_{s\in S}\mathrm{\mid }{\bar{\delta }}_f^{g,{\pi }^{\mathrm{\prime }}}(s)\mathrm{\mid }$ and

$L_{\pi ,f}^g({\pi }^{\mathrm{\prime }}):={\sum }_{s\in S}{d}^{\pi }(s)({\bar{\delta }}_f^{g,{\pi }^{\mathrm{\prime }}}(s)-{\bar{\delta }}_f^{g,\pi }(s)),D_{\pi ,f}^{\pm ,g}({\pi }^{\mathrm{\prime }}):=\frac{L_{\pi ,f}^g({\pi }^{\mathrm{\prime }})}{1-\gamma }\pm \frac{2\gamma {ϵ}_f^g({\pi }^{\mathrm{\prime }})}{(1-\gamma {)}^2}{\sum }_{s\in S}{d}^{\pi }(s){\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi ),$

where ${\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi ):=\frac{1}{2}{\sum }_{a\in A(s)}\mathrm{\mid }{\pi }^{\mathrm{\prime }}(a\mid s)-\pi (a\mid s)\mathrm{\mid }$. Then

$D_{\pi ,f}^{-,g}({\pi }^{\mathrm{\prime }})\le J_g^{{\pi }^{\mathrm{\prime }}}(\mu )-J_g^{\pi }(\mu )\le D_{\pi ,f}^{+,g}({\pi }^{\mathrm{\prime }})\mathrm{.}$

These total-variation bounds are choice-free. Under the additional Axiom of Choice, define

${\bar{D}}_{\mathrm{K}\mathrm{L}}^{\pi }({\pi }^{\mathrm{\prime }}\mathrm{\parallel }\pi ):={\sum }_{s:d^{\pi }(s)>0}{d}^{\pi }(s)D_{\mathrm{K}\mathrm{L}}({\pi }^{\mathrm{\prime }}(\cdot \mid s)\mathrm{\parallel }\pi (\cdot \mid s)),$

using natural logarithms and $+\mathrm{\infty }$ when the first action law is not absolutely continuous with respect to the second. The same inequalities hold after replacing ${\sum }_s{d}^{\pi }(s){\mathrm{TV}}_s({\pi }^{\mathrm{\prime }},\pi )$ by $\sqrt{{\bar{D}}_{\mathrm{K}\mathrm{L}}^{\pi }({\pi }^{\mathrm{\prime }}\mathrm{\parallel }\pi )\mathrm{/}2}$; when the average KL is infinite, these KL-form inequalities are interpreted as the trivial extended bounds $-\mathrm{\infty }\le J_g^{{\pi }^{\mathrm{\prime }}}(\mu )-J_g^{\pi }(\mu )\le +\mathrm{\infty }$. Taking $g=r$ gives the reward bound, and taking $g=c_i$ gives the corresponding bound for each discounted cost.

The finite transition model, bounded signals, initial law, and discount.

Expected discounted-cost feasibility constraint: The expected discounted signal objective $J_g^{\pi }(\mu )$.

Normalized discounted state occupancy: The normalized occupancy $d^{\pi }$.

The AC-conditional finite-action Pinsker/Jensen bound.

The resolvent estimate for the change of discounted state occupancy.

Performance-difference identity for an arbitrary bounded baseline: The exact performance-difference identity for arbitrary bounded $f$.

Achiam et al., Constrained Policy Optimization, §5.1.

Achiam et al., Constrained Policy Optimization, supplementary material, Appendix 10.1.