Discounted-Probe Clamped Policy Iteration

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$.