# Discounted-Probe Clamped Policy Iteration

- ID: 1823
- Canonical URL: https://synthcore.org/idea/1823/discounted-probe-clamped-policy-iteration
- API JSON: https://synthcore.org/api/idea/1823.json
- API Markdown: https://synthcore.org/api/idea/1823.md
- Verification status: failed_benchmark
- Source: [arXiv:2608.05047](https://arxiv.org/abs/2608.05047)
- Category: dynamics
- Solves: stability, sample-efficiency, accuracy
- ML areas: rl, optimizer, training-dynamics
- Math tags: dynamical-systems, control-theory, probability, optimization
- Ratings: usefulness 8/10; difficulty 5/10; novelty 7/10

## Idea description

For sparse terminal-reward RL, first solve a discounted version of the fixed-policy Bellman equation to detect states with zero probability of ever reaching success. Clamp these dead states to value zero, retain successful terminal states at value one, and then run undiscounted stochastic policy evaluation and greedy improvement on the reduced state space. The clamp removes the nonunique harmonic solutions that make direct undiscounted TD unstable or initialization-dependent.

## Mathematical statement

Let $S$ be a finite state space, $A$ the action set, $Z\subseteq S$ the success or accepting states, $P(s'\mid s,a)$ the transition kernel, and $\pi(a\mid s)$ a stationary policy. Define $P_\pi(s,s')=\sum_a\pi(a\mid s)P(s'\mid s,a)$ and the reachability value $V^\pi(s)=\Pr_s^\pi(\tau_Z<\infty)$, where $\tau_Z$ is the first hitting time of $Z$. For a discount factor $0<\gamma<1$, compute the unique discounted probe $u^\pi_\gamma$ satisfying $u^\pi_\gamma(s)=1$ for $s\in Z$ and $u^\pi_\gamma(s)=\gamma\sum_{s'}P_\pi(s,s')u^\pi_\gamma(s')$ otherwise. Define the dead-state clamp set $D_\pi=\{s\notin Z:u^\pi_\gamma(s)=0\}$; in a finite MDP this identifies states with no positive-probability path to $Z$ under $\pi$. The clamped undiscounted evaluation solves $V^\pi(s)=1$ on $Z$, $V^\pi(s)=0$ on $D_\pi$, and $V^\pi(s)=\sum_{s'}P_\pi(s,s')V^\pi(s')$ elsewhere. Policy improvement uses $Q^\pi(s,a)=\sum_{s'}P(s'\mid s,a)V^\pi(s')$ and $\pi_{new}(s)\in\arg\max_a Q^\pi(s,a)$.

## Key formulas

- $$u^\pi_\gamma(s)=\begin{cases}1,&s\in Z,\\ \gamma\sum_{s'\in S}P_\pi(s,s')u^\pi_\gamma(s'),&s\notin Z,\end{cases}\qquad 0<\gamma<1.$$
- $$D_\pi=\{s\in S\setminus Z:u^\pi_\gamma(s)=0\},\qquad V^\pi(s)=\begin{cases}1,&s\in Z,\\0,&s\in D_\pi,\\ \sum_{s'}P_\pi(s,s')V^\pi(s'),&\text{otherwise.}\end{cases}$$
- $$Q^\pi(s,a)=\sum_{s'}P(s'\mid s,a)V^\pi(s'),\qquad \pi_{k+1}(s)\in\arg\max_{a\in A}Q^{\pi_k}(s,a).$$
- $$\|T_{\pi,\gamma}u-T_{\pi,\gamma}v\|_\infty\leq\gamma\|u-v\|_\infty,$$ whereas the undiscounted operator generally has Lipschitz constant $1$ and may have nonunique fixed points.

## Implementation notes

1. Integration point: implement this as a tabular or neural fitted-RL policy-iteration wrapper for sparse success/failure tasks. For an sc-LTL task, construct the product observation $(x_t,q_t)$, where $x_t$ is the environment state or embedding and $q_t$ is the DFA progress state; define $Z$ as accepting product states. For a first implementation use a tabular grid world or a small MLP critic, not a large benchmark. 2. Pseudocode: initialize policy $\pi$. For each policy-iteration round, estimate the discounted probe by TD: for sampled transition $(s,a,s')$, use target $y=1$ if $s\in Z$, otherwise $y=\gamma u_\theta(s')$; regress $u_\theta(s)$ toward $y$. Estimate $D_\pi$ using an absolute threshold $\varepsilon_D$, for example $D_\pi=\{s:u_\theta(s)<\varepsilon_D\}$, with a confidence requirement such as five consecutive low estimates. Freeze $V(s)=1$ on $Z$ and $V(s)=0$ on $D_\pi$. Evaluate the remaining states with undiscounted TD or Monte Carlo returns until the sup-norm change is below $\varepsilon_V$. Estimate $Q(s,a)$ from successor values or one-step samples, then replace the policy by the greedy action with deterministic tie-breaking. Repeat until no action changes. 3. Computed from the paper: the discounted contraction mechanism, the dead-state clamp, and the undiscounted policy-evaluation/improvement structure. Estimated empirically: transition expectations, $u_\gamma$, $V^\pi$, the dead-state threshold, and confidence in the clamp. For neural critics, use separate probe and reachability heads and stop-gradient through the clamp mask. 4. First cheap experiment: compare this method with undiscounted Q-learning, discounted Q-learning with $\gamma=0.99$, and Monte Carlo policy evaluation on a $10\times10$ stochastic grid world containing traps, dead regions, and a goal. Run 100 random seeds and measure success probability, value error against exact dynamic programming, and dependence on critic initialization. The quantitative prediction is that direct undiscounted TD will show initialization-dependent values in closed non-goal regions, while the clamped method will converge to the same reachability values across seeds; after the discounted probe has separated $u_\gamma=0$ from positive states, the residual evaluation error should decay geometrically in episodic environments and the number of policy changes should be finite. Vary $\gamma$ and test that the detected dead-state set stabilizes once $\gamma\geq0.9$; false clamp rate should be below 5% when the probe estimation error is below half the chosen threshold $\varepsilon_D$.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: inconclusive
- Verdict: Built a reusable tabular Discounted-Probe Clamped Policy Iteration module and a numerical verification experiment. The mechanism manifested: observed live-block contraction rates matched predicted gamma*rho values to numerical precision, the dead-state mask was stable across gamma=0.1 through 0.999, and clamping removed initialization dependence. The clamped method achieved approximately 7.1e-13 mean sup-norm error versus approximately 1.06 for direct undiscounted iteration on the toy MDP.

### Mechanism check

- Verdict: Built a reusable tabular Discounted-Probe Clamped Policy Iteration module and a numerical verification experiment. The mechanism manifested: observed live-block contraction rates matched predicted gamma*rho values to numerical precision, the dead-state mask was stable across gamma=0.1 through 0.999, and clamping removed initialization dependence. The clamped method achieved approximately 7.1e-13 mean sup-norm error versus approximately 1.06 for direct undiscounted iteration on the toy MDP.
- Confidence: 9/10
- Limitations: Only a small hand-designed tabular fixed-policy MDP and a tiny policy-improvement smoke test were evaluated. The experiment used exact linear solves rather than sampled TD or neural critics, and did not test a 10x10 grid world, 100 independent seeds, wall-clock or sample efficiency, noisy probe thresholds, or false-clamp rates under estimation error.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.35875
- Paired wins: 6/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/653/bench_report.json)
- [custom_terminal_reachability.py](https://synthcore.org/code/653/custom_terminal_reachability.py)
- [discounted_probe_clamped.py](https://synthcore.org/code/653/discounted_probe_clamped.py)
- [report.md](https://synthcore.org/code/653/report.md)
- [report_bench_2026-08-31T210124.md](https://synthcore.org/code/653/report_bench_2026-08-31T210124.md)
- [results.json](https://synthcore.org/code/653/results.json)
- [run_bench.py](https://synthcore.org/code/653/run_bench.py)
- [verify.py](https://synthcore.org/code/653/verify.py)
- [Download all files as ZIP](https://synthcore.org/download/653)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.