# Error-budgeted adaptive rollout allocation

- ID: 2050
- Canonical URL: https://synthcore.org/idea/2050/error-budgeted-adaptive-rollout-allocation
- API JSON: https://synthcore.org/api/idea/2050.json
- API Markdown: https://synthcore.org/api/idea/2050.md
- Verification status: unverified
- Source: [arXiv:2608.09494](https://arxiv.org/abs/2608.09494)
- Category: training
- Solves: speedup, sample-efficiency, stability
- ML areas: training, loss, curriculum
- Math tags: probability, numerical-analysis, approximation-theory
- Ratings: usefulness 6/10; difficulty 4/10; novelty 7/10

## Idea description

Use the paper's explicit separation of geometric, truncation, and Monte Carlo errors to adapt the number of Walk-on-Spheres paths and rollout depth per training point. Points close to the boundary receive short, low-cost rollouts, while points with high estimated target variance receive additional paths only when the resulting accuracy justifies their cost.

## Mathematical statement

The extracted uniform error bound separates a geometric term $(L_{1}^{0}+\lVert h_{1}\rVert_{\infty})\operatorname{diam}(D)\delta+L_{2}^{0}d^{1/2}\operatorname{diam}(D)^{1/2}\delta^{1/2}$, a truncation term $C_{\mathrm{trunc}}(1+\beta^{2}\delta^{2}/(2\operatorname{diam}(D)^{2}))^{-M}$, and sampling terms containing $C_{1}/K$ and $C_{2}(M)/(KM^{2})$. Here $L_{1}^{0},L_{2}^{0}$ are time and space Lipschitz constants of the boundary data, $L_{1}^{1},L_{2}^{1}$ are corresponding constants for the source, $\lVert h_{0}\rVert_{\infty}$ and $\lVert h_{1}\rVert_{\infty}$ are sup norms, $d$ is dimension, $\delta$ is the stopping-radius threshold, $M$ is maximum rollout depth, $K$ is path count, $\beta$ is a domain-dependent parameter, and $D_{\mathrm{diam}}=\operatorname{diam}(D)$. A practical local uncertainty estimate is the sample variance $\widehat v(x)=(K-1)^{-1}\sum_{i=1}^{K}(Y_i(x)-\bar Y(x))^{2}$, where $Y_i$ is one rollout return and $\bar Y$ is the sample mean. The exponential decay in $M$ gives a direct truncation-depth rule, while the inverse dependence on $K$ gives a variance-based path-count rule.

## Key formulas

- $$\operatorname{Err}\le C_{\mathrm{geom}}\delta+C_{\mathrm{trunc}}\left(1+\frac{\beta^{2}\delta^{2}}{2\operatorname{diam}(D)^{2}}\right)^{-M}+\frac{C_{1}}{K}+\frac{C_{2}(M)}{KM^{2}}.$$
- $$\widehat v(x)=\frac{1}{K-1}\sum_{i=1}^{K}\left(Y_i(x)-\bar Y(x)\right)^2,\qquad \bar Y(x)=\frac{1}{K}\sum_{i=1}^{K}Y_i(x).$$
- $$M(x)=\left\lceil\frac{\log(C_{\mathrm{trunc}}/\varepsilon_{\mathrm{trunc}})}{\log\left(1+\beta^{2}\delta^{2}/(2\operatorname{diam}(D)^{2})\right)}\right\rceil,\qquad K(x)=\left\lceil\frac{\widehat v(x)}{\varepsilon_{\mathrm{MC}}^{2}}\right\rceil.$$

## Implementation notes

(1) Integration point: modify the stochastic-target data loader rather than the network architecture. For every interior training point $x$, dynamically choose rollout depth $M(x)$ and path count $K(x)$ before constructing its regression target. The same allocation can be used during validation, where computation should concentrate on difficult regions. (2) Pseudocode: begin with a pilot rollout of depth $M_{0}$ and $K_{0}$ paths. Compute returns $Y_i(x)$, mean $\bar Y(x)$, and variance $\widehat v(x)$. Choose a stopping radius $\delta$, an estimated truncation constant $\widehat C_{\mathrm{trunc}}$, and domain diameter $D_{\mathrm{diam}}$. Set $M(x)=\lceil\log(\widehat C_{\mathrm{trunc}}/\varepsilon_{\mathrm{trunc}})/\log(1+\widehat\beta^{2}\delta^{2}/(2D_{\mathrm{diam}}^{2}))\rceil$, clipped to $[M_{0},M_{\max}]$. Set $K(x)=\max(K_{0},\lceil\widehat v(x)/\varepsilon_{\mathrm{MC}}^{2}\rceil)$, clipped to $[K_{0},K_{\max}]$. Reuse pilot paths and draw only missing paths. Optionally weight the squared loss by $1/(\widehat v(x)+\eta)$, with small $\eta>0$, to prevent noisy targets from dominating. (3) Compute from the mathematics: geometric cutoff, sphere times, truncation schedule, and functional dependence on $M$ and $K$. Estimate empirically: $\widehat\beta$, error constants, target variance, and rollout cost. Maintain variance estimates with an exponential moving average over distance-to-boundary bins. (4) First experiment: use a four-dimensional unit-ball Poisson problem with known analytic solution. Compare fixed $(M,K)$ against adaptive allocation at equal total rollout evaluations. Log test error, target variance, average $M$ and $K$, and wall-clock time. Success means the adaptive method reaches the same error with at least 25 percent fewer rollouts, or gives lower error at equal budget without unstable minibatch losses.

## Disclaimer

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