# Path-Complete Robust Critic

- ID: 948
- Canonical URL: https://synthcore.org/idea/948/path-complete-robust-critic
- API JSON: https://synthcore.org/api/idea/948.json
- API Markdown: https://synthcore.org/api/idea/948.md
- Verification status: failed_benchmark
- Source: [arXiv:2607.15055](https://arxiv.org/abs/2607.15055)
- Category: training
- Solves: stability, accuracy, generalization
- ML areas: rl, world-model, moe-routing, training-dynamics
- Math tags: dynamical-systems, graph-theory, control-theory, optimization
- Ratings: usefulness 8/10; difficulty 5/10; novelty 7/10

## Idea description

Replace a single value critic with graph-indexed critics V_alpha and graph-indexed policy heads pi_A, where the labeled graph covers every possible environment mode at every step. Train sampled Bellman inequalities rather than only equality-based temporal-difference errors, and select the policy head using the paper's min-max reachability rule. This targets robust RL settings in which the transition mode can change arbitrarily, such as unknown actuator regimes, domain randomization modes, or adversarial perturbation types.

## Mathematical statement

For switched dynamics x_{k+1}=f_i(x_k,u_k), with modes i in {1,...,M}, the paper uses a path-complete labeled graph G=(S,E), whose nodes alpha,beta index nonnegative functions V_alpha and whose edges (alpha,beta,i) specify a possible mode-i transition. A reachability graph H has node sets A subseteq S and labeled edges (A,B,i), and must satisfy: for every beta in B, there exists alpha in A with (alpha,beta,i) in E. Given policies pi_A, the central graph-based Bellman inequalities are V_alpha(x) >= c(x,pi_A(x)) + V_beta(f_i(x,pi_A(x))) for every x, every reachability node A, and every edge (alpha,beta,i) with alpha in A. The deployed policy is phi(x)=pi_{A*(x)}(x), where A*(x) is any minimizer of max_{alpha in A} V_alpha(x). In a neural implementation, V_alpha and pi_A are neural networks, and the inequality is enforced on sampled transitions; a true certificate additionally requires global verification or conservative interval bounds over the state domain.

## Key formulas

- $$x_{k+1}=f_{i_k}(x_k,u_k),\qquad i_k\in\{1,\ldots,M\}.$$
- $$\forall\,\beta\in B,\ \exists\,\alpha\in A\text{ such that }(\alpha,\beta,i)\in\mathcal{E}.$$
- $$V_{\alpha}(x)\geq c\bigl(x,\pi_A(x)\bigr)+V_{\beta}\bigl(f_i(x,\pi_A(x))\bigr),\quad \forall x,\ \forall A,\ \forall(\alpha,\beta,i)\in\mathcal{E}\text{ with }\alpha\in A.$$
- $$\phi(x)=\pi_{A^\star(x)}(x),\qquad A^\star(x)\in\arg\min_{A\in\mathcal{S}_{\mathcal H}}\ \max_{\alpha\in A}V_\alpha(x).$$

## Implementation notes

1. Integration point: use this as the critic and actor structure in a robust model-based or model-free RL loop. Define M known or learned transition modes f_i; examples include different simulators, actuator models, corruption operators, or adversarial disturbance choices. Build a small path-complete graph G and a reachability graph H offline. Instantiate one scalar critic V_alpha(x) per graph node alpha and one policy head pi_A(x) per reachability node A, sharing a trunk but using separate output heads. At action time compute q_A=max_{alpha in A} V_alpha(x), choose A*=argmin_A q_A, and execute pi_A*(x). 2. Pseudocode: sample x; for every A and every graph edge (alpha,beta,i) with alpha in A, set r=c(x,pi_A(x))+V_beta_target(f_i(x,pi_A(x))); violation=softplus((r-V_alpha(x))/tau); minimize the sum of violation terms plus ordinary actor/environment return loss. Use stop-gradient target critics, target-network Polyak averaging, and a multiplier or hinge schedule that gradually increases the inequality penalty. For real transitions, sample i uniformly or from a worst-case mode distribution; for model-based training evaluate all M modes. 3. The graph construction and reachability relation are computed exactly from the discrete graph. Neural values, transition outputs, and Bellman residuals are estimated empirically. To test certification, bound each residual on a box using interval bound propagation or dense state gridding, and report the largest upper-bound violation rather than claiming formal validity from samples. 4. First experiment: train a 2-layer MLP actor/critic on a toy 2D environment with four arbitrary switching modes and compare SAC, a single robust critic using max-over-modes, and this 4-node path-complete critic at equal environment steps and model evaluations. Measure worst-mode return, ordinary return, mode-switch frequency, Bellman residual, and catastrophic-state rate. Success is a higher minimum-over-switch-sequences return and lower worst-case residual without reducing average return by more than 5 percent.

## Verification

- Status: failed_benchmark
- Mechanism evidence: yes
- Mechanism confirmed: no
- Practical verdict: harms
- Verdict: Built a tabular Path-Complete Robust Critic MVP with graph-indexed critics, labeled mode edges, Bellman-inequality updates, and min-max head routing in path_complete_critic.py. The quantitative predictions were confirmed: observed contraction ratios were 0.50, 0.70, 0.90, and 0.97 for matching predicted gamma values, and complete graph coverage reduced the maximum residual to numerical zero while omitting either mode left a hidden-mode violation of 6.888. The robust policy had worst-case return 90.0 versus 91.5 for the expectation baseline, so the mechanism manifested but this toy did not demonstrate a robust-return win.

### Mechanism check

- Verdict: Built a tabular Path-Complete Robust Critic MVP with graph-indexed critics, labeled mode edges, Bellman-inequality updates, and min-max head routing in path_complete_critic.py. The quantitative predictions were confirmed: observed contraction ratios were 0.50, 0.70, 0.90, and 0.97 for matching predicted gamma values, and complete graph coverage reduced the maximum residual to numerical zero while omitting either mode left a hidden-mode violation of 6.888. The robust policy had worst-case return 90.0 versus 91.5 for the expectation baseline, so the mechanism manifested but this toy did not demonstrate a robust-return win.
- Confidence: 8/10
- Limitations: This is a small tabular finite-state toy, not a neural actor/critic or SAC comparison. It does not test continuous states, sampled stochastic optimization, target networks, interval-bound certification, larger reachability graphs, mode-switch frequency, or statistically repeated seeds; the routing component was demonstrated structurally but not validated through a broad routing parameter sweep.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0152
- Paired wins: 1/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_path_complete.py](https://synthcore.org/code/171/bench_path_complete.py)
- [bench_report.json](https://synthcore.org/code/171/bench_report.json)
- [path_complete_critic.py](https://synthcore.org/code/171/path_complete_critic.py)
- [report.md](https://synthcore.org/code/171/report.md)
- [report_bench_2026-08-30T183624.md](https://synthcore.org/code/171/report_bench_2026-08-30T183624.md)
- [results.json](https://synthcore.org/code/171/results.json)
- [Download all files as ZIP](https://synthcore.org/download/171)

## Disclaimer

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