Introduction
Self-driving laboratories run experimental campaigns in chemistry and biology with automated equipment and a learning algorithm that decides what to do next [2 ] . Each episode is a real experiment, in which the controller measures the state of a reactor or culture, sets inputs such as a feed rate, and is often rewarded only once the batch is complete [39 , 10 ] . Each campaign is therefore a finite-horizon Markov decision process (MDP) with continuous states and inputs and unknown dynamics. The controller must learn from tens to hundreds of episodes, too few to also tune the hyperparameters of the learner.
Reinforcement learning (RL) with Gaussian processes (GPs) usually learns a model of the dynamics and plans through it [16 , 10 , 6 ] , but model errors compound over the horizon [30 , 44 ] , especially when the reward arrives only at the end. We instead place a GP prior [46 ] on the Q Q Q -function [55 ] , which the controller maximises directly to choose its inputs. Similarly, Bayesian optimisation models the objective of an experiment rather than the process behind it [48 ] .
Q-learning moves its estimate towards each new Bellman target by a learning rate, which must be tuned for each problem [23 ] . The noise of a laboratory process is rarely known in advance and changes between instruments, batches of material and operating conditions [4 , 43 , 25 ] . Kalman temporal difference (TD) methods set the rate to a Kalman gain by treating each target as a noisy measurement of the Q-function, but tune the noise variance of the targets in place of the rate [23 , 22 , 52 ] , and existing GP Q-learning methods tune the rate itself [7 , 13 ] . Variance-aware value iteration instead weights each target by the inverse of its variance, which in theory needs fewer samples [40 ] (Yin et al. 2022). Heteroscedastic Gaussian Process Q-learning (HGPQ) makes this practical. It estimates the variance of each target with a heteroscedastic GP and uses it in the Kalman gain, computed as GP regression. Our contributions are:
Method. HGPQ, a GP Q-learning method whose learning rate is the Kalman gain and whose target variances are estimated by a heteroscedastic GP, so that no learning rate is tuned.
Theory. A high-probability bound on the error of the posterior mean, uniform over the explored region, for per-target variances that are assigned when a target is collected.
Results. Pooled over five benchmarks, HGPQ approaches the best return found by any method in fewer episodes than GP, kernel and deep RL baselines with equal or larger budgets.
Related work. The bias-adjusted Kalman filter (BAKF) and the optimal stepsize algorithm for approximate value iteration (OSAVI) [23 , 47 ] , GP temporal differences (GPTD) and GP SARSA (GPSARSA) [18 , 19 ] and Kalman temporal differences (KTD) for Q-learning [22 ] set the TD learning rate from a single noise variance. Kalman filter Q-learning [52 ] , assumed density filtering Q-learning [31 ] and deep ensembles [36 ] give each target its own noise or weight, but from the epistemic uncertainty of the successor’s value. HGPQ instead follows variance-aware value iteration [40 ] (Yin et al. 2022). This weights each target by the inverse of an estimated variance of the next value plus a floor, and it has sharper regret and sample complexity than unweighted regression [28 , 3 ] (Zhou et al. 2021). HGPQ estimates these variances nonparametrically with a heteroscedastic GP [24 , 34 ] . Like optimistic kernel value iteration [32 , 14 ] (Yang et al. 2020), whose regret is order-optimal for Matérn kernels [53 ] , HGPQ fits a regularised estimate per time step [33 ] . Like fitted Q-iteration [20 ] , it regresses Bellman targets on stored transitions, and unlike GP dynamic programming [15 ] , which models both the value function and the dynamics with GPs, it needs no model of the dynamics. We bound its error uniformly over the explored region of the state-input space.
Problem setting and Gaussian processes
Finite-horizon MDPs. At time steps t = 0 , … , T − 1 t = 0, \ldots, T - 1 t = 0 , … , T − 1 the controller observes a state x t \mathbf{x}_t x t in a compact set X ⊂ R d x \mathcal{X} \subset\mathbb{R}^{d_x} X ⊂ R d x and applies an input u t \mathbf{u}_t u t from a box U ⊂ R d u \mathcal{U} \subset\mathbb{R}^{d_u} U ⊂ R d u . We write z = ( x , u ) \mathbf{z} = (\mathbf{x}, \mathbf{u}) z = ( x , u ) , Z : = X × U \mathcal{Z} := \mathcal{X} \times\mathcal{U} Z := X × U and d : = d x + d u d := d_x + d_u d := d x + d u . The pair z t \mathbf{z}_t z t produces a random stage reward r t ∈ [ r min , r max ] r_t \in[r_{\min}, r_{\max}] r t ∈ [ r m i n , r m a x ] with mean r ˉ t ( z ) : = E [ r t ∣ z t = z ] \bar{r}_t(\mathbf{z}) := \mathbb{E}[r_t \mid\mathbf{z}_t = \mathbf{z}] r ˉ t ( z ) := E [ r t ∣ z t = z ] and a random next state x t + 1 ∼ P t ( ⋅ ∣ z t ) \mathbf{x}_{t+1} \sim P_t(\cdot\mid\mathbf{z}_t) x t + 1 ∼ P t ( ⋅ ∣ z t ) , with P t P_t P t the transition kernel, and the initial state is drawn from a density p 0 p_0 p 0 . The final state x T \mathbf{x}_T x T produces a random terminal reward r T ∈ [ r min T , r max T ] r_T \in[r_{\min}^T, r_{\max}^T] r T ∈ [ r m i n T , r m a x T ] with mean r ˉ T ( x ) : = E [ r T ∣ x T = x ] \bar{r}_T(\mathbf{x}) := \mathbb{E}[r_T \mid\mathbf{x}_T = \mathbf{x}] r ˉ T ( x ) := E [ r T ∣ x T = x ] , such as the yield of a batch. The goal is a policy π = ( π 0 , … , π T − 1 ) \pi= (\pi_0, \ldots, \pi_{T-1}) π = ( π 0 , … , π T − 1 ) that maximises the expected return E π [ ∑ t = 0 T − 1 r t + r T ] \mathbb{E}_{\pi}\left[\sum_{t=0}^{T-1} r_t + r_T\right] E π [ ∑ t = 0 T − 1 r t + r T ] . The optimal Q-function Q t ∗ ( z ) Q_t^*(\mathbf{z}) Q t ∗ ( z ) , the expected return of applying u \mathbf{u} u in state x \mathbf{x} x at time step t t t and acting optimally afterwards, satisfies the Bellman equation, solved backwards from the terminal value V T ∗ : = r ˉ T V_T^* := \bar{r}_T V T ∗ := r ˉ T ,
Q t ∗ ( z ) = r ˉ t ( z ) + E x ′ ∼ P t ( ⋅ ∣ z ) [ V t + 1 ∗ ( x ′ ) ] , V t ∗ ( x ) : = max u ∈ U Q t ∗ ( x , u ) , t = T − 1 , … , 0 (1) Q_t^*(\mathbf{z}) = \bar{r}_t(\mathbf{z}) + \mathbb{E}_{\mathbf{x}' \sim P_t(\cdot\mid\mathbf{z})}\left[V_{t+1}^*(\mathbf{x}')\right], \qquad V_t^*(\mathbf{x}) := \max_{\mathbf{u} \in\mathcal{U}} Q_t^*(\mathbf{x}, \mathbf{u}), \qquad t = T-1, \ldots, 0 \tag*{(1)} Q t ∗ ( z ) = r ˉ t ( z ) + E x ′ ∼ P t ( ⋅ ∣ z ) [ V t + 1 ∗ ( x ′ ) ] , V t ∗ ( x ) := u ∈ U max Q t ∗ ( x , u ) , t = T − 1 , … , 0 (1)
with r ˉ T ≡ 0 \bar{r}_T \equiv0 r ˉ T ≡ 0 without a terminal reward. The greedy policy π t ∗ ( x ) ∈ arg max u Q t ∗ ( x , u ) \pi_t^*(\mathbf{x}) \in\arg\max_{\mathbf{u}} Q_t^*(\mathbf{x}, \mathbf{u}) π t ∗ ( x ) ∈ arg max u Q t ∗ ( x , u ) is optimal, so HGPQ learns Q 0 ∗ , … , Q T − 1 ∗ Q_0^*, \ldots, Q_{T-1}^* Q 0 ∗ , … , Q T − 1 ∗ from data and needs no model of the dynamics.
Gaussian process regression. Under a GP prior f ∼ G P ( 0 , κ ) f \sim\mathcal{GP}(0, \kappa) f ∼ G P ( 0 , κ ) on f : Z → R f : \mathcal{Z} \to\mathbb{R} f : Z → R (Rasmussen and Williams, [46 ] ), given observations o i = f ( z i ) + η i o_i = f(\mathbf{z}_i) + \eta_i o i = f ( z i ) + η i , i = 1 , … , n i = 1, \ldots, n i = 1 , … , n , with independent zero-mean noise of variance λ i \lambda_i λ i , write o : = ( o 1 , … , o n ) T \mathbf{o} := (o_1, \ldots, o_n)^{\mathsf{T}} o := ( o 1 , … , o n ) T , Λ : = diag ( λ 1 , … , λ n ) \Lambda:= \operatorname{diag}(\lambda_1, \ldots, \lambda_n) Λ := diag ( λ 1 , … , λ n ) , K : = [ κ ( z i , z j ) ] i , j ≤ n K := [\kappa(\mathbf{z}_i,\mathbf{z}_j)]_{i,j \le n} K := [ κ ( z i , z j ) ] i , j ≤ n and κ n ( z ) : = ( κ ( z 1 , z ) , … , κ ( z n , z ) ) T \kappa_n(\mathbf{z}) := (\kappa(\mathbf{z}_1,\mathbf{z}), \ldots, \kappa(\mathbf{z}_n,\mathbf{z}))^{\mathsf{T}} κ n ( z ) := ( κ ( z 1 , z ) , … , κ ( z n , z ) ) T . Conditioning on o \mathbf{o} o gives the posterior G P ( μ , Σ ) \mathcal{GP}(\mu,\Sigma) G P ( μ , Σ ) with
μ ( z ) = κ n ( z ) T ( K + Λ ) − 1 o , Σ ( z , z ′ ) = κ ( z , z ′ ) − κ n ( z ) T ( K + Λ ) − 1 κ n ( z ′ ) (2) \mu(\mathbf{z}) = \kappa_n(\mathbf{z})^{\mathsf{T}}(K+\Lambda)^{-1}\mathbf{o}, \qquad\Sigma(\mathbf{z},\mathbf{z}') = \kappa(\mathbf{z},\mathbf{z}') - \kappa_n(\mathbf{z})^{\mathsf{T}}(K+\Lambda)^{-1}\kappa_n(\mathbf{z}') \tag*{(2)} μ ( z ) = κ n ( z ) T ( K + Λ ) − 1 o , Σ ( z , z ′ ) = κ ( z , z ′ ) − κ n ( z ) T ( K + Λ ) − 1 κ n ( z ′ ) (2)
and we write σ 2 ( z ) : = Σ ( z , z ) \sigma^2(\mathbf{z}) := \Sigma(\mathbf{z},\mathbf{z}) σ 2 ( z ) := Σ ( z , z ) . The noise is heteroscedastic when the λ i \lambda_i λ i differ. We use the Matérn-5 / 2 5/2 5/2 kernel κ ( z , z ′ ) = σ f 2 k 5 / 2 ( ∥ diag ( ℓ ) − 1 ( z − z ′ ) ∥ ) \kappa(\mathbf{z},\mathbf{z}') = \sigma_f^2 k_{5/2}(\lVert\operatorname{diag}(\boldsymbol{\ell})^{-1}(\mathbf{z}-\mathbf{z}')\rVert) κ ( z , z ′ ) = σ f 2 k 5/2 (∥ diag ( ℓ ) − 1 ( z − z ′ )∥) with signal variance σ f 2 \sigma_f^2 σ f 2 and one lengthscale ℓ j \ell_j ℓ j per dimension of z \mathbf{z} z , except on the LMDP, where the kernel is linear in fixed features (Appendix § 8 ).
Heteroscedastic Gaussian Process Q-learning
Bellman targets
Like least-squares value iteration (Jin et al., [32 ] ) and kernel optimistic least-squares value iteration (KOVI, Yang et al., 2020), HGPQ keeps one GP per time step, Q t ∼ G P ( μ t , Σ t ) Q_t \sim\mathcal{GP}(\mu_t,\Sigma_t) Q t ∼ G P ( μ t , Σ t ) for t = 0 , … , T − 1 t = 0, \ldots, T-1 t = 0 , … , T − 1 , refitted backwards after each episode, and a dataset D t \mathcal{D}_t D t of the transitions observed at time step t t t . The GPs have independent priors, because the Q-function of a finite-horizon problem differs between time steps, which are coupled only through the targets. Each stored transition gives the Bellman target, the Q-learning target with the GP mean in place of a table of values,
y t , i = r i + V t + 1 ( x i ′ ) , V t + 1 ( x ) : = max u ∈ U μ t + 1 ( x , u ) (3) y_{t,i} = r_i + V_{t+1}(\mathbf{x}_i'), \qquad V_{t+1}(\mathbf{x}) := \max_{\mathbf{u} \in\mathcal{U}} \mu_{t+1}(\mathbf{x}, \mathbf{u}) \tag*{(3)} y t , i = r i + V t + 1 ( x i ′ ) , V t + 1 ( x ) := u ∈ U max μ t + 1 ( x , u ) (3)
where V T V_T V T is the terminal value. Our benchmarks give the reward of the final state on the last transition, so V T ≡ 0 V_T \equiv0 V T ≡ 0 , and only the synthetic MDPs of § 5.2 have a known terminal reward, V T = r ˉ T V_T = \bar{r}_T V T = r ˉ T . Appendix § 8 covers other terminal rewards and the clipping of V t + 1 V_{t+1} V t + 1 .
Learning rate from the GP posterior
Tabular Q-learning (Watkins and Dayan, [55 ] ) moves a stored value Q ^ t ( z i ) \hat{Q}_t(\mathbf{z}_i) Q ^ t ( z i ) towards the target of a transition ( z i , r i , x i ′ ) (\mathbf{z}_i,r_i,\mathbf{x}_i') ( z i , r i , x i ′ ) observed at time step t t t by α ( y t , i − Q ^ t ( z i ) ) \alpha\left(y_{t,i}-\hat{Q}_t(\mathbf{z}_i)\right) α ( y t , i − Q ^ t ( z i ) ) , with a learning rate α ∈ ( 0 , 1 ] \alpha\in(0,1] α ∈ ( 0 , 1 ] that must often be tuned. We instead hold a GP belief Q t ∼ G P ( μ t , Σ t ) Q_t \sim\mathcal{GP}(\mu_t,\Sigma_t) Q t ∼ G P ( μ t , Σ t ) about the Q-function at time step t t t and treat each target as a noisy measurement of it,
y t , i = r i + max u ∈ U μ t + 1 ( x i ′ , u ) = Q t ( z i ) + η t , i , E [ η t , i ] = 0 , Var ( η t , i ) = λ t , i (4) y_{t,i} = r_i + \max_{\mathbf{u} \in\mathcal{U}} \mu_{t+1}(\mathbf{x}_i',\mathbf{u}) = Q_t(\mathbf{z}_i) + \eta_{t,i}, \qquad\mathbb{E}[\eta_{t,i}] = 0, \qquad\operatorname{Var}(\eta_{t,i}) = \lambda_{t,i} \tag*{(4)} y t , i = r i + u ∈ U max μ t + 1 ( x i ′ , u ) = Q t ( z i ) + η t , i , E [ η t , i ] = 0 , Var ( η t , i ) = λ t , i (4)
with η t , i \eta_{t,i} η t , i independent of Q t Q_t Q t , the model of § 2 with f = Q t f = Q_t f = Q t . Write μ t ( i ) \mu_t^{(i)} μ t ( i ) and Σ t ( i ) \Sigma_t^{(i)} Σ t ( i ) for the belief after the first i i i targets, starting from the prior, μ t ( 0 ) ≡ 0 \mu_t^{(0)} \equiv0 μ t ( 0 ) ≡ 0 and Σ t ( 0 ) = κ \Sigma_t^{(0)} = \kappa Σ t ( 0 ) = κ . Where tabular Q-learning moves one stored value by the scalar rate α \alpha α , HGPQ moves the whole mean and covariance by the Kalman gain α t ( i ) \alpha_t^{(i)} α t ( i ) , a function of the state–input pair z \mathbf{z} z ,
α t ( i ) ( z ) : = Σ t ( i − 1 ) ( z , z i ) Σ t ( i − 1 ) ( z i , z i ) + λ t , i , (5) \alpha_t^{(i)}(\mathbf{z}) := \frac{\Sigma_t^{(i-1)}(\mathbf{z}, \mathbf{z}_i)}{\Sigma_t^{(i-1)}(\mathbf{z}_i, \mathbf{z}_i) + \lambda_{t,i}}, \tag*{(5)} α t ( i ) ( z ) := Σ t ( i − 1 ) ( z i , z i ) + λ t , i Σ t ( i − 1 ) ( z , z i ) , (5)
μ t ( i ) ( z ) = μ t ( i − 1 ) ( z ) + α t ( i ) ( z ) ( y t , i − μ t ( i − 1 ) ( z i ) ) , \mu_t^{(i)}(\mathbf{z}) = \mu_t^{(i-1)}(\mathbf{z}) + \alpha_t^{(i)}(\mathbf{z})\left(y_{t,i} - \mu_t^{(i-1)}(\mathbf{z}_i)\right), μ t ( i ) ( z ) = μ t ( i − 1 ) ( z ) + α t ( i ) ( z ) ( y t , i − μ t ( i − 1 ) ( z i ) ) ,
Σ t ( i ) ( z , z ′ ) = Σ t ( i − 1 ) ( z , z ′ ) − α t ( i ) ( z ) Σ t ( i − 1 ) ( z i , z ′ ) , (6) \Sigma_t^{(i)}(\mathbf{z},\mathbf{z}') = \Sigma_t^{(i-1)}(\mathbf{z},\mathbf{z}') - \alpha_t^{(i)}(\mathbf{z})\Sigma_t^{(i-1)}(\mathbf{z}_i,\mathbf{z}'), \tag*{(6)} Σ t ( i ) ( z , z ′ ) = Σ t ( i − 1 ) ( z , z ′ ) − α t ( i ) ( z ) Σ t ( i − 1 ) ( z i , z ′ ) , (6)
which minimises the mean squared error of the update at every pair (Proposition 2, Appendix A).
Its value at the measured pair, α t ( i ) ( z i ) ∈ [ 0 , 1 ) \alpha_t^{(i)}(\mathbf{z}_i) \in[0,1) α t ( i ) ( z i ) ∈ [ 0 , 1 ) , plays the role of the rate α \alpha α . It is near one for an uncertain estimate and a precise target, and near zero for a precise estimate or a noisy target. It spreads the update to nearby pairs through the posterior covariance (Figure 1 ). It also shrinks without a schedule as the variance falls. After all n n n targets, in any order, the updates (6) give the GP posterior (2) , written μ t \mu_t μ t and Σ t \Sigma_t Σ t , with observations y t : = ( y t , 1 , … , y t , n ) T \mathbf{y}_t := (y_{t,1}, \ldots, y_{t,n})^\mathsf{T} y t := ( y t , 1 , … , y t , n ) T and noise Λ t : = diag ( λ t , 1 , … , λ t , n ) \Lambda_t := \operatorname{diag}(\lambda_{t,1}, \ldots, \lambda_{t,n}) Λ t := diag ( λ t , 1 , … , λ t , n ) (Proposition 3). GP Q-learning with the Kalman gain is therefore linear-Gaussian Bayesian inference, which HGPQ carries out in closed form as one GP regression. The targets of the previous time step bootstrap from μ t \mu_t μ t , and the policy acts on it.
Figure 1. Posterior mean before and after one new target y i y_i y i , with a small (trusted) or a large (untrusted) variance λ i \lambda_i λ i . The Kalman gain moves the mean towards a trusted target and spreads the update to nearby pairs.
Heteroscedastic target noise
Decomposition of the target error. The Kalman gain is the best learning rate only when λ t , i \lambda_{t,i} λ t , i is the mean squared error of the target about Q t ∗ ( z i ) Q_t^*(\mathbf{z}_i) Q t ∗ ( z i ) (Proposition 2), and the joint update of Proposition 3 treats the errors of different targets as independent. With V t + 1 ∗ : = max u Q t + 1 ∗ ( ⋅ , u ) V_{t+1}^* := \max_u Q_{t+1}^*(\cdot,u) V t + 1 ∗ := max u Q t + 1 ∗ ( ⋅ , u ) the optimal value, V T ∗ : = r ˉ T V_T^* := \bar{r}_T V T ∗ := r ˉ T and r ˉ t \bar{r}_t r ˉ t the mean reward of § 2 , this error has three parts,
y t , i − Q t ∗ ( z i ) = r i − r ˉ t ( z i ) ⏟ reward + V t + 1 ( x i ′ ) − E [ V t + 1 ( X ′ ) ∣ z i ] ⏟ next state + E [ V t + 1 ( X ′ ) − V t + 1 ∗ ( X ′ ) ∣ z i ] ⏟ next estimate . (7) y_{t,i} - Q_t^*(z_i) = \underbrace{r_i - \bar{r}_t(z_i)}_{\text{reward}} + \underbrace{V_{t+1}(x_i') - \mathbb{E}\left[V_{t+1}(X') \mid z_i\right]}_{\text{next state}} + \underbrace{\mathbb{E}\left[V_{t+1}(X') - V_{t+1}^*(X') \mid z_i\right]}_{\text{next estimate}}. \tag*{(7)} y t , i − Q t ∗ ( z i ) = reward r i − r ˉ t ( z i ) + next state V t + 1 ( x i ′ ) − E [ V t + 1 ( X ′ ) ∣ z i ] + next estimate E [ V t + 1 ( X ′ ) − V t + 1 ∗ ( X ′ ) ∣ z i ] . (7)
The reward and the next state are drawn independently for each transition, so the first two parts are independent between targets. The third is the error of one function, μ t + 1 \mu_{t+1} μ t + 1 , averaged over nearby next states. Targets whose next states are close therefore share it, and a larger variance per target does not average it away (Appendix A.§ 3 ).
Variance of each target. HGPQ gives each target the variance of the part of its error that is independent between targets,
λ t , i = σ r 2 + ω t ( z i ) , t = T − 1 , … , 0 , (8) \lambda_{t,i} = \sigma_r^2 + \omega_t(z_i), \qquad t = T-1,\ldots,0, \tag*{(8)} λ t , i = σ r 2 + ω t ( z i ) , t = T − 1 , … , 0 , (8)
and leaves the shared error as a bias, which vanishes as μ t + 1 \mu_{t+1} μ t + 1 converges to Q t + 1 ∗ Q_{t+1}^* Q t + 1 ∗ . Here σ r 2 \sigma_r^2 σ r 2 is a small floor for the reward noise, such as the measurement noise of a yield sensor, and ω t ( z i ) ≥ 0 \omega_t(z_i) \ge0 ω t ( z i ) ≥ 0 is the remaining independent error, which has two sources. The first is the spread of the next value over the next states reached from z i z_i z i . It varies with the pair because the process noise depends on the operating conditions [25 ] and the gradient of the value function varies across the state space. The second, where the transitions are nearly deterministic, is the bootstrap error where V t + 1 V_{t+1} V t + 1 has large gradients, such as at a step or where the maximising input switches. A small error in where μ t + 1 \mu_{t+1} μ t + 1 places such a step gives the targets on either side errors of opposite sign.
Heteroscedastic GP estimate. HGPQ estimates ω t \omega_t ω t from the leave-one-out residual of each target, its difference from the prediction of the GP fitted to all other targets. With A t : = ( K + Λ t ) − 1 A_t := (K + \Lambda_t)^{-1} A t := ( K + Λ t ) − 1 for the targets of time step t t t and their current variances, the residual and its predictive variance follow in closed form from one fit [46 ] ,
e i : = y t , i − μ t , − i ( z i ) = [ A t y t ] i [ A t ] i i , σ t , − i 2 ( z i ) + λ t , i = 1 [ A t ] i i . (9) e_i := y_{t,i} - \mu_{t,-i}(z_i) = \frac{[A_t y_t]_i}{[A_t]_{ii}}, \qquad\sigma^2_{t,-i}(z_i) + \lambda_{t,i} = \frac{1}{[A_t]_{ii}}. \tag*{(9)} e i := y t , i − μ t , − i ( z i ) = [ A t ] ii [ A t y t ] i , σ t , − i 2 ( z i ) + λ t , i = [ A t ] ii 1 . (9)
An error shared by targets at nearby inputs is already predicted by the GP fitted to the other targets, so it cancels in the residual, which therefore measures the target’s independent error. As in heteroscedastic GP regression [24 , 34 ] , a second GP g t g_t g t , with its own kernel and Gaussian noise level, is fitted to the pairs ( z i , log e i 2 ) (z_i, \log e_i^2) ( z i , log e i 2 ) . With m t m_t m t its posterior mean, shifted by the constant − E [ log χ 1 2 ] -\mathbb{E}[\log\chi_1^2] − E [ log χ 1 2 ] that corrects for the logarithm (Appendix § 8 ),
ω t ( z i ) = max { 0 , exp ( m t ( z i ) ) − σ t , − i 2 ( z i ) − σ r 2 } , (10) \omega_t(z_i) = \max\left\{0, \exp\left(m_t(z_i)\right) - \sigma^2_{t,-i}(z_i) - \sigma_r^2\right\}, \tag*{(10)} ω t ( z i ) = max { 0 , exp ( m t ( z i ) ) − σ t , − i 2 ( z i ) − σ r 2 } , (10)
the expected squared residual less the predictive variance of the GP and the floor. The variances and the kernel are then fitted in turn.
Algorithm
Algorithm 1 summarises HGPQ. The targets of time step t t t depend on μ t + 1 \mu_{t+1} μ t + 1 , so each backward pass fits the GP’s from the terminal value V T V_T V T down to t = 0 t=0 t = 0 , as the Bellman equation (1) is solved,
μ t + 1 → (3), (8) targets, variances ( y t , Λ t ) → (2) GP fit ( μ t , Σ t ) , t = T − 1 , … , 0. (11) \mu_{t+1} \xrightarrow[\text{(3), (8)}]{\text{targets, variances}} (y_t,\Lambda_t) \xrightarrow[\text{(2)}]{\text{GP fit}} (\mu_t,\Sigma_t), \qquad t = T-1,\ldots,0. \tag*{(11)} μ t + 1 targets, variances (3), (8) ( y t , Λ t ) GP fit (2) ( μ t , Σ t ) , t = T − 1 , … , 0. (11)
Algorithm 1: Heteroscedastic Gaussian Process Q-learning (HGPQ)
Input: horizon T T T , kernel family κ \kappa κ , reward noise σ r 2 \sigma_r^2 σ r 2 , exploration probability ϵ \epsilon ϵ , episodes N N N , and datasets D t \mathcal{D}_t D t of transitions from N 0 N_0 N 0 episodes with space-filling inputs.
for episode n = 1 , … , N n=1,\ldots,N n = 1 , … , N do
fit the terminal GP to the pairs ( x T , r T ) (x_T,r_T) ( x T , r T ) in D T \mathcal{D}_T D T , if used (Appendix B) // terminal value
for t = T − 1 , … , 0 t=T-1,\ldots,0 t = T − 1 , … , 0 do // backward pass
for each ( z i , r i , x i ′ ) ∈ D t (z_i,r_i,x'_i)\in\mathcal{D}_t ( z i , r i , x i ′ ) ∈ D t do
y t , i ← r i + V t + 1 ( x i ′ ) y_{t,i}\leftarrow r_i+V_{t+1}(x'_i) y t , i ← r i + V t + 1 ( x i ′ ) // target (3)
end
fit the kernel by marginal likelihood and ω t \omega_t ω t by a heteroscedastic GP // noise model
Λ t ← diag ( λ t , i ) \Lambda_t\leftarrow\operatorname{diag}(\lambda_{t,i}) Λ t ← diag ( λ t , i ) with λ t , i = σ r 2 + ω t ( z i ) \lambda_{t,i}=\sigma_r^2+\omega_t(z_i) λ t , i = σ r 2 + ω t ( z i ) // target variances
( μ t , Σ t ) ← (\mu_t,\Sigma_t)\leftarrow ( μ t , Σ t ) ← posterior (2) of Q t Q_t Q t given y t y_t y t with noise Λ t \Lambda_t Λ t // (6) on every target
end
for t = 0 , … , T − 1 t=0,\ldots,T-1 t = 0 , … , T − 1 do // rollout
draw Q ~ t ∼ G P ( μ t , Σ t ) \widetilde{Q}_t\sim\mathcal{GP}(\mu_t,\Sigma_t) Q t ∼ G P ( μ t , Σ t ) // Thompson sampling
u t ← arg max u Q ~ t ( x t , u ) u_t\leftarrow\arg\max_u\widetilde{Q}_t(x_t,u) u t ← arg max u Q t ( x t , u ) , or uniform on U \mathcal{U} U with probability ϵ \epsilon ϵ
Apply u t u_t u t , observe r t r_t r t and x t + 1 x_{t+1} x t + 1 , and add ( z t , r t , x t + 1 ) (z_t,r_t,x_{t+1}) ( z t , r t , x t + 1 ) to D t \mathcal{D}_t D t
end
observe the terminal reward r T r_T r T of x T x_T x T , if any, and add ( x T , r T ) (x_T,r_T) ( x T , r T ) to D T \mathcal{D}_T D T
end
Output: after a final backward pass, the greedy policy π ^ t ( x ) ∈ arg max u μ t ( x , u ) \hat{\pi}_t(x)\in\arg\max_u\mu_t(x,u) π ^ t ( x ) ∈ arg max u μ t ( x , u ) .
Each posterior supplies the targets and variances of the time step before it, with μ t + 1 \mu_{t+1} μ t + 1 held fixed, and after each episode the whole chain is refitted from the prior, since a change in μ t + 1 \mu_{t+1} μ t + 1 changes every target of time step t t t . After N 0 N_0 N 0 initial episodes with space-filling inputs, the behaviour policy applies a uniformly random input with probability ϵ \epsilon ϵ , which maintains coverage, and otherwise maximises a posterior sample Q ~ t \widetilde{Q}_t Q t (Thompson, [50 ] ) drawn by pathwise conditioning (Wilson et al., 2020, 2021) (Appendix B).
Convergence in function space
The greedy policy evaluates μ t \mu_t μ t at pairs never visited, so μ t \mu_t μ t must be accurate over a whole region. Write μ t n \mu_t^n μ t n for the mean after n n n episodes. The analysis takes rewards in [ 0 , 1 ] [0,1] [ 0 , 1 ] , exact maximisation, a fixed kernel, unstandardised targets and N 0 = 0 N_0=0 N 0 = 0 , and gives each target a base variance λ t , i ∈ [ λ − , λ + ] \lambda_{t,i}\in[\lambda_-,\lambda_+] λ t , i ∈ [ λ − , λ + ] , λ − > 0 \lambda_->0 λ − > 0 , fixed before the outcome of its transition is drawn and multiplied after n n n episodes by n ζ n^\zeta n ζ , ζ ∈ [ 0 , 1 ) \zeta\in[0,1) ζ ∈ [ 0 , 1 ) , with ζ = 0 \zeta=0 ζ = 0 in Algorithm 1. It assumes (Assumption 2, Appendix A.4) Markov transitions, Bellman completeness in the reproducing kernel Hilbert space of the kernel, as in kernel value iteration ([32 ] (Yang et al. 2020)), a kernel approximation property with exponent q q q and constant L κ ≥ 0 L_\kappa\geq0 L κ ≥ 0 (q = 1 q=1 q = 1 and L κ > 0 L_\kappa>0 L κ > 0 for the Matérn-5/2 kernel), and visited pairs with a density bounded below on regions Z t : = X t × U \mathcal{Z}_t:=\mathcal{X}_t\times\mathcal{U} Z t := X t × U whose next states stay in X t + 1 \mathcal{X}_{t+1} X t + 1 .
Theorem 1 (Uniform convergence) Let Assumption 2 hold, let ζ ∈ [ 0 , 1 ) \zeta\in[0,1) ζ ∈ [ 0 , 1 ) and δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , and let θ : = q / ( 2 q + d ) \theta:=q/(2q+d) θ := q / ( 2 q + d ) if L κ > 0 L_\kappa>0 L κ > 0 and θ : = 1 / 2 \theta:=1/2 θ := 1/2 if L κ = 0 L_\kappa=0 L κ = 0 . There are constants C σ , t C_{\sigma,t} C σ , t , a burn-in n 0 ( δ ) n_0(\delta) n 0 ( δ ) and widths β t , n ( δ ) \beta_{t,n}(\delta) β t , n ( δ ) (Definitions 5 and 6) such that, with probability at least 1 − 2 δ 1-2\delta 1 − 2 δ , for all n ≥ n 0 ( δ ) n\geq n_0(\delta) n ≥ n 0 ( δ ) and all time steps t t t ,
sup z ∈ Z t ∣ μ t n ( z ) − Q t ∗ ( z ) ∣ ≤ n − ( 1 − ζ ) θ ∑ j = t T − 1 C σ , j β j , n ( δ ) . (12) \sup_{z\in\mathcal{Z}_t}\left|\mu_t^n(z)-Q_t^*(z)\right|\leq n^{-(1-\zeta)\theta}\sum_{j=t}^{T-1}C_{\sigma,j}\,\beta_{j,n}(\delta). \tag*{(12)} z ∈ Z t sup ∣ μ t n ( z ) − Q t ∗ ( z ) ∣ ≤ n − ( 1 − ζ ) θ j = t ∑ T − 1 C σ , j β j , n ( δ ) . (12)
If n − ( 1 − ζ ) θ β j , n ( δ ) → 0 for every j and every δ ∈ ( 0 , 1 ) , then μ t n → Q t ∗ uniformly on Z t almost surely. \text{If } n^{-(1-\zeta)\theta}\beta_{j,n}(\delta) \to0 \text{ for every } j \text{ and every } \delta\in(0,1), \text{ then } \mu_t^n \to Q_t^* \text{ uniformly on } \mathcal{Z}_t \text{ almost surely.} If n − ( 1 − ζ ) θ β j , n ( δ ) → 0 for every j and every δ ∈ ( 0 , 1 ) , then μ t n → Q t ∗ uniformly on Z t almost surely.
Here the constant C σ , t C_{\sigma,t} C σ , t grows with the largest variance λ + \lambda_+ λ + and with the inverse of the density of the visited pairs, the burn-in n 0 ( δ ) n_0(\delta) n 0 ( δ ) is the number of episodes after which the visited pairs cover every region Z t \mathcal{Z}_t Z t at the resolution of the bound, and the width β t , n ( δ ) \beta_{t,n}(\delta) β t , n ( δ ) adds the norm bound of the completeness assumption, a discretisation term and a noise term that grows with the information gain of the kernel. The proof is in Appendix A.§ 4 . It covers variances assigned when a target is collected and a fixed kernel, not the re-estimated variances or the refitted kernel of Algorithm 1. For the Matérn-5/2 kernel with uniformly bounded eigenfunctions, q = 1 q = 1 q = 1 and θ = 1 / ( 2 + d ) \theta= 1/(2+d) θ = 1/ ( 2 + d ) , and without a schedule the error is of order n − ( 10 − d 2 ) / ( 2 ( 2 + d ) ( 5 + d ) ) n^{-(10-d^2)/(2(2+d)(5+d))} n − ( 10 − d 2 ) / ( 2 ( 2 + d ) ( 5 + d )) up to logarithmic factors, which tends to zero for d ≤ 3 d \le3 d ≤ 3 . With ζ = d / ( 5 + 2 d ) \zeta= d/(5+2d) ζ = d / ( 5 + 2 d ) it is of order n − ( 5 + d ) / ( ( 2 + d ) ( 5 + 2 d ) ) n^{-(5+d)/((2+d)(5+2d))} n − ( 5 + d ) / (( 2 + d ) ( 5 + 2 d )) in every dimension (Corollary 13). The burn-in grows at least exponentially with d d d .
Experiments
Experimental setup
Benchmarks. The non-stationary linear MDP (LMDP) has a reward whose input coefficient changes sign every two time steps. The semi-batch reactor ([9 , 8 ] ) and photosynthetic biomass production ([8 , 10 ] ) are nonlinear processes rewarded at the end of the batch and penalised whenever a state constraint is violated, with rate constants that fluctuate between time steps, which imitates unmodelled changes in mass transfer and mixing. The inverted pendulum is swung up and rewarded for its final state, and in target tracking the final distance of a spring-mass system to a target is penalised. All have random initial states and process noise, and horizons of 8 to 20 time steps (Appendix C).
Baselines and protocol. We compare HGPQ with GP Q-learning with a scheduled or a constant learning rate (GPQ-SLR and GPQ-CLR, [7 ] ), with KOVI (Yang et al., 2020), with GPTD in its SARSA form [19 ] , with KTD, with Kalman filter Q-learning (KFQL, [52 ] ), and with DQN [41 ] , Ensemble-DQN [42 ] , DDPG [37 ] , TD3 [21 ] and SAC [26 ] . Table 1 compares their updates with HGPQ’s. All methods start from the same N 0 N_0 N 0 initial episodes (5 on the LMDP, 10 on the pendulum and target tracking and 20 on the reactor and biomass production), which the budgets below do not count, are tuned on ten separate seeds and run on thirty seeds, or fifty for the comparison of target variances on the pendulum and target tracking (Appendix § 11 ). The budgets favour the kernel and deep RL baselines: 300 episodes for HGPQ and the other GP Q-learning methods, 750 for KOVI and GPTD, and 2000 for KTD, KFQL and deep RL. HGPQ stops at 300 episodes because an exact refit costs O ( n 3 ) O(n^3) O ( n 3 ) per time step, and Sparse HGPQ (Appendix § 12 ) runs for 600 episodes at linear cost.
Table 1. Update rules at time step t t t , with y i y_i y i the Bellman target of transition i i i . GPQ-CLR moves a stored value Q ^ i \hat{Q}_i Q ^ i towards y i y_i y i with a tuned rate α \alpha α and fits a GP to these values, KTD filters the weights w \mathbf{w} w of fixed features ϕ i \phi_i ϕ i with Kalman gain k \mathbf{k} k , GPTD observes each reward as a difference of successive values plus noise η t \eta_t η t , and KOVI adds c c c posterior standard deviations of the next GP to its target. All but GPQ-CLR move the estimate by a Kalman gain and differ in what they observe and with what noise.
Measuring sample efficiency. The normalised regret is the gap to the best return that any method found, rather than to the true optimum, divided by the gap between that return and the starting return. As in optimiser benchmarking [27 ] , a run reaches each of 15 thresholds at the first episode at which its normalised regret, averaged over the last ten episodes, falls below it.
Target variances in two synthetic MDPs
Two synthetic MDPs with a scalar state and 150 random transitions per time step separate the two kinds of target error that ω t \omega_t ω t estimates (Figure 2 , Appendix § 10 ). In A, the transitions from states below about − 0.2 -0.2 − 0.2 are noisy. HGPQ’s variances follow the noise of each target, whereas one noise level fitted by marginal likelihood is too small for the noisy targets and too large for the others. Where the transitions are almost noise-free (x ≥ 0 x \ge0 x ≥ 0 ), HGPQ’s value error is therefore half that with one noise level and about 25 times smaller than with the floor alone (Table 3 ). In B, the transitions are nearly deterministic and a step in the terminal reward is carried back as a sharp rise in V t ∗ V_t^* V t ∗ . A small error in where μ t + 1 \mu_{t+1} μ t + 1 places the step gives the targets on either side errors of opposite sign. HGPQ gives them larger variances, whereas one noise level collapses to the floor, and for x ≥ 0 x \ge0 x ≥ 0 , beyond the step, its value error is less than a quarter of that with one noise level, at the price of a larger error for x < 0 x < 0 x < 0 , which contains the step. Its greedy policy is closer to the optimal return in B and about as close in A (Appendix § 10 ).
Figure 2. Two synthetic MDPs with a scalar state (§ 5.2 ), one dataset each. In A the transitions from states below about − 0.2 -0.2 − 0.2 are noisy, and in B they are nearly deterministic and the terminal reward is a step. HGPQ’s variance of each target of time step 1 and the noise of that target, against the state of its transition, one noise level per time step fitted by marginal likelihood, and the optimal value V 1 ∗ V_1^* V 1 ∗ (right axis) with, in A, one standard deviation of the target noise about it. The floor in these MDPs is σ r 2 = 10 − 4 \sigma_r^2 = 10^{-4} σ r 2 = 1 0 − 4 (Appendix § 10 ), the lower edge of the variance axes.
Table 3. Synthetic MDPs: return gap of the greedy policy and mean absolute value error at time step 1, averaged over twenty datasets.
Sample efficiency
Pooled over the benchmarks, HGPQ comes closest to the best returns in the fewest episodes (Figure 3 ). It reaches 69% of the thresholds within 150 episodes and 77% within 300, more than every baseline after its full budget of 750 or 2000 episodes except Ensemble-DQN, which reaches as many after 2000. GPQ-SLR and GPQ-CLR, which update a table of stored values with a scheduled or tuned learning rate, reach about half the thresholds by the end of their 300-episode budget. Per benchmark, HGPQ is the fastest on the pendulum and target tracking. On the reactor it reaches more thresholds within 300 episodes than any baseline within the same budget, and only DQN, Ensemble-DQN and KFQL reach more, after 2000 episodes. On biomass production GPQ-CLR matches HGPQ within 150 episodes, and only SAC reaches more, after 2000. On the LMDP, whose value is linear, KOVI, KTD and KFQL do about as well as HGPQ (Appendix H). Sparse HGPQ, which uses sparse GPs with 256 inducing points so that a refit costs time linear in n n n , remains the fastest method over 600 episodes on the pendulum and target tracking with up to ten times the process noise, more pendulums or longer horizons, in all but one setting (Appendix § 12 ).
Figure 3. Fraction of runs whose normalised regret is below each of 15 thresholds from 0.5 to 0.01, pooled over the benchmarks (30 seeds, 95% bands, crosses at the end of a budget).
Per-target and constant variances
Figure 4 compares HGPQ’s per-target variances with two homoscedastic choices, with its GP, exploration and settings unchanged. The floor σ r 2 \sigma_r^2 σ r 2 alone, a homoscedastic GP regression with too little noise, is worse on all four benchmarks, and so is a constant variance σ r 2 + s κ max \sigma_r^2 + s\kappa_{\max} σ r 2 + s κ m a x , with κ max \kappa_{\max} κ m a x the prior variance of the kernel and the scale s s s tuned per benchmark. On the pendulum and target tracking, which are nearly deterministic and whose values have large gradients, most of the error of the targets is bootstrap error, as in MDP B. On the reactor and biomass production the fluctuating reaction and growth rates make the noise depend on the state, as in MDP A, and HGPQ’s final return is well above that of the tuned constant, 0.059 against 0.007 on the reactor. HGPQ shares only the floor σ r 2 \sigma_r^2 σ r 2 with the constant, and a single floor σ r = 10 − 3 \sigma_r = 10^{-3} σ r = 1 0 − 3 does not significantly lower the final return on any benchmark tested (Appendix § 13 ).
Figure 4. Final return after 300 episodes of HGPQ, of the floor σ r 2 \sigma_r^2 σ r 2 alone and of a constant variance σ r 2 + s κ max \sigma_r^2 + s\kappa_{\max} σ r 2 + s κ m a x with the scale s s s tuned per benchmark and κ max \kappa_{\max} κ m a x the prior variance of the kernel (mean, 95% interval and seeds, 30 seeds, 50 on the pendulum and target tracking). Returns of the reactor and biomass production are on symmetric logarithmic axes, and costs of the pendulum and target tracking on inverted logarithmic axes.
Adding the next GP’s variance σ t + 1 2 \sigma_{t+1}^2 σ t + 1 2 , which is large while the next estimate is poor, to every target’s variance slows early learning on the pendulum and target tracking and changes the final return by at most 5%, except for a lower final cost on target tracking. A tuned constant plus σ t + 1 2 \sigma_{t+1}^2 σ t + 1 2 matches HGPQ’s final return only on these two benchmarks (Appendix § 13 ).
Conclusion
We show that GP Q-learning needs no tuned learning rate. The optimal rate is the Kalman gain, which one GP regression applies to every stored transition. HGPQ gives each Bellman target the variance of the part of its error that is independent between targets, estimated by a heteroscedastic GP: the noise of the process where it is noisy, and the local bootstrap error. Pooled over five benchmarks, it needs fewer episodes than GP, kernel and deep RL baselines, and on the reactor and biomass benchmarks, where the noise depends on the state, it outperforms a constant variance tuned per benchmark. The analysis assumes a fixed kernel and variances set when a target is collected. The O ( n 3 ) O(n^3) O ( n 3 ) cost of an exact refit per time step is small beside an experiment lasting hours, and Sparse HGPQ makes it linear in n n n . The benchmarks penalise violations of the state constraints rather than prevent them, and future work will handle the constraints with feasibility backups.
Proofs
Optimality of the Kalman gain
The next result concerns a single update from a belief G P ( μ , Σ ) \mathcal{GP}(\mu,\Sigma) G P ( μ , Σ ) . With μ = μ t ( i − 1 ) \mu=\mu_t^{(i-1)} μ = μ t ( i − 1 ) , Σ = Σ t ( i − 1 ) \Sigma=\Sigma_t^{(i-1)} Σ = Σ t ( i − 1 ) , y = y t , i y=y_{t,i} y = y t , i and λ = λ t , i \lambda=\lambda_{t,i} λ = λ t , i , its learning rate is the gain (5) and its update is (6) .
Proposition 2 (Kalman gain) Let Q ∼ G P ( μ , Σ ) Q\sim\mathcal{GP}(\mu,\Sigma) Q ∼ G P ( μ , Σ ) and y = Q ( z i ) + η y=Q(z_i)+\eta y = Q ( z i ) + η , with η \eta η independent of Q Q Q , E [ η ] = 0 \mathbb{E}[\eta]=0 E [ η ] = 0 and Var ( η ) = λ > 0 \operatorname{Var}(\eta)=\lambda>0 Var ( η ) = λ > 0 .
(a) For every z ∈ Z z\in\mathcal{Z} z ∈ Z , among the estimates μ ( z ) + a ( y − μ ( z i ) ) \mu(z)+a\left(y-\mu(z_i)\right) μ ( z ) + a ( y − μ ( z i ) ) with a ∈ R a\in\mathbb{R} a ∈ R , the mean squared error E [ ( Q ( z ) − μ ( z ) − a ( y − μ ( z i ) ) ) 2 ] \mathbb{E}\left[\left(Q(z)-\mu(z)-a\left(y-\mu(z_i)\right)\right)^2\right] E [ ( Q ( z ) − μ ( z ) − a ( y − μ ( z i ) ) ) 2 ] is smallest for the learning rate
a = α ( z ; z i ) : = Σ ( z , z i ) σ 2 ( z i ) + λ . a=\alpha(z;z_i):=\frac{\Sigma(z,z_i)}{\sigma^2(z_i)+\lambda}. a = α ( z ; z i ) := σ 2 ( z i ) + λ Σ ( z , z i ) . The updated estimate μ + ( z ) : = μ ( z ) + α ( z ; z i ) ( y − μ ( z i ) ) \mu^+(z):=\mu(z)+\alpha(z;z_i)\left(y-\mu(z_i)\right) μ + ( z ) := μ ( z ) + α ( z ; z i ) ( y − μ ( z i ) ) has error covariance Σ + ( z , z ′ ) = Σ ( z , z ′ ) − α ( z ; z i ) Σ ( z i , z ′ ) \Sigma^+(z,z')=\Sigma(z,z')-\alpha(z;z_i)\Sigma(z_i,z') Σ + ( z , z ′ ) = Σ ( z , z ′ ) − α ( z ; z i ) Σ ( z i , z ′ ) . If Q Q Q and η \eta η are Gaussian, μ + \mu^+ μ + and Σ + \Sigma^+ Σ + are the exact posterior mean and covariance of Q Q Q given y y y .
(b) At the measured pair the learning rate is α ( z i ; z i ) = σ 2 ( z i ) / ( σ 2 ( z i ) + λ ) ∈ [ 0 , 1 ) \alpha(z_i;z_i)=\sigma^2(z_i)/(\sigma^2(z_i)+\lambda)\in[0,1) α ( z i ; z i ) = σ 2 ( z i ) / ( σ 2 ( z i ) + λ ) ∈ [ 0 , 1 ) . If the same pair is measured n n n times, starting from variance σ ˉ 2 > 0 \bar{\sigma}^2>0 σ ˉ 2 > 0 there, the learning rate of the n n n -th update is
α n = 1 n + λ / σ ˉ 2 (13) \alpha_n=\frac{1}{n+\lambda/\bar{\sigma}^2} \tag*{(13)} α n = n + λ / σ ˉ 2 1 (13)
Proof. Part (a). Let e : = y − μ ( z i ) e := y - \mu(\mathbf{z}_i) e := y − μ ( z i ) . Since η \eta η is independent of Q Q Q with mean zero, Var ( e ) = σ 2 ( z i ) + λ \operatorname{Var}(e) = \sigma^2(\mathbf{z}_i) + \lambda Var ( e ) = σ 2 ( z i ) + λ and Cov ( Q ( z ) , e ) = Σ ( z , z i ) \operatorname{Cov}(Q(\mathbf{z}), e) = \Sigma(\mathbf{z}, \mathbf{z}_i) Cov ( Q ( z ) , e ) = Σ ( z , z i ) , so the mean squared error is the parabola
σ 2 ( z ) − 2 a Σ ( z , z i ) + a 2 ( σ 2 ( z i ) + λ ) \sigma^2(\mathbf{z}) - 2a\Sigma(\mathbf{z}, \mathbf{z}_i) + a^2\left(\sigma^2(\mathbf{z}_i) + \lambda\right) σ 2 ( z ) − 2 a Σ ( z , z i ) + a 2 ( σ 2 ( z i ) + λ )
in a a a , whose unique minimiser is α ( z ; z i ) \alpha(\mathbf{z}; \mathbf{z}_i) α ( z ; z i ) . With c : = Σ ( z , z i ) Σ ( z i , z ′ ) / ( σ 2 ( z i ) + λ ) c := \Sigma(\mathbf{z}, \mathbf{z}_i)\Sigma(\mathbf{z}_i, \mathbf{z}')/(\sigma^2(\mathbf{z}_i) + \lambda) c := Σ ( z , z i ) Σ ( z i , z ′ ) / ( σ 2 ( z i ) + λ ) , expanding the covariance of Q ( z ) − μ + ( z ) = Q ( z ) − μ ( z ) − α ( z ; z i ) e Q(\mathbf{z}) - \mu^+(\mathbf{z}) = Q(\mathbf{z}) - \mu(\mathbf{z}) - \alpha(\mathbf{z}; \mathbf{z}_i)e Q ( z ) − μ + ( z ) = Q ( z ) − μ ( z ) − α ( z ; z i ) e and Q ( z ′ ) − μ + ( z ′ ) Q(\mathbf{z}') - \mu^+(\mathbf{z}') Q ( z ′ ) − μ + ( z ′ ) gives Σ ( z , z ′ ) − 2 c + c = Σ + ( z , z ′ ) \Sigma(\mathbf{z}, \mathbf{z}') - 2c + c = \Sigma^+(\mathbf{z}, \mathbf{z}') Σ ( z , z ′ ) − 2 c + c = Σ + ( z , z ′ ) , since each cross term equals − c -c − c and the last term equals c c c . In the Gaussian case ( Q ( z ) , Q ( z ′ ) , y ) (Q(\mathbf{z}), Q(\mathbf{z}'), y) ( Q ( z ) , Q ( z ′ ) , y ) is jointly Gaussian, and conditioning on y y y gives μ + \mu^+ μ + and Σ + \Sigma^+ Σ + .
Part (b). The gain at z i \mathbf{z}_i z i lies in [ 0 , 1 ) [0,1) [ 0 , 1 ) because λ > 0 \lambda> 0 λ > 0 . By part (a) the variance at the measured pair becomes σ 2 ( z i ) λ / ( σ 2 ( z i ) + λ ) \sigma^2(\mathbf{z}_i)\lambda/(\sigma^2(\mathbf{z}_i) + \lambda) σ 2 ( z i ) λ / ( σ 2 ( z i ) + λ ) , so each measurement adds 1 / λ 1/\lambda 1/ λ to the precision there. The variance before the n n n -th update is therefore σ ˉ n − 1 2 = ( 1 / σ ˉ 2 + ( n − 1 ) / λ ) − 1 \bar{\sigma}_{n-1}^2 = (1/\bar{\sigma}^2 + (n-1)/\lambda)^{-1} σ ˉ n − 1 2 = ( 1/ σ ˉ 2 + ( n − 1 ) / λ ) − 1 , and α n = 1 / ( 1 + λ / σ ˉ n − 1 2 ) = 1 / ( n + λ / σ ˉ 2 ) \alpha_n = 1/(1+\lambda/\bar{\sigma}_{n-1}^2) = 1/(n+\lambda/\bar{\sigma}^2) α n = 1/ ( 1 + λ / σ ˉ n − 1 2 ) = 1/ ( n + λ / σ ˉ 2 ) .
Kalman updates as linear-Gaussian Bayesian inference
Applying Proposition 2 to the stored transitions one at a time is a Kalman filter with a constant state, the Q-function, and hence recursive Bayesian regression ([22 ] ).
Proposition 3 (Kalman updates are linear-Gaussian Bayesian inference). Applying the update of Proposition 2(a), starting from G P ( 0 , κ ) \mathcal{GP}(0,\kappa) G P ( 0 , κ ) , once for each of ( z i , y i , λ i ) (\mathbf{z}_i, y_i, \lambda_i) ( z i , y i , λ i ) , i = 1 , … , n i = 1,\ldots,n i = 1 , … , n , in any order, gives the posterior of the model y i = Q ( z i ) + η i y_i = Q(\mathbf{z}_i) + \eta_i y i = Q ( z i ) + η i with independent η i ∼ N ( 0 , λ i ) \eta_i \sim\mathcal{N}(0,\lambda_i) η i ∼ N ( 0 , λ i ) , namely (2) with o = y \mathbf{o} = \mathbf{y} o = y and Λ = diag ( λ 1 , … , λ n ) \Lambda= \operatorname{diag}(\lambda_1,\ldots,\lambda_n) Λ = diag ( λ 1 , … , λ n ) . The result is the same for any noise distribution with these variances.
Proof. The updates and (2) are algebraic in the inputs, targets, variances and kernel, so it suffices to take Gaussian noise. Then each update is exact conditioning on one target (Proposition 2(a)), and since the noise terms are independent given Q Q Q , conditioning one target at a time in any order equals conditioning on y \mathbf{y} y at once. With Cov ( y ) = K + Λ \operatorname{Cov}(\mathbf{y}) = K + \Lambda Cov ( y ) = K + Λ and Cov ( Q ( z ) , y ) = κ n ( z ) T \operatorname{Cov}(Q(\mathbf{z}), \mathbf{y}) = \boldsymbol{\kappa}_n(\mathbf{z})^\mathsf{T} Cov ( Q ( z ) , y ) = κ n ( z ) T , this gives (2) .
Derivation of the target variances
The measurement model (4) treats the error of each target,
η t , i : = y t , i − Q ∗ ( z i ) = r i − r ˉ t ( z i ) ⏟ a i + V t + 1 ( x i ′ ) − E [ V t + 1 ( x ′ ) ∣ z i ] ⏟ b i + E [ V t + 1 ( x ′ ) − V t + 1 ∗ ( x ′ ) ∣ z i ] ⏟ c i , \begin{aligned}
\eta_{t,i} &:= y_{t,i} - Q^*(\mathbf{z}_i) \\
&= \underbrace{r_i - \bar{r}_t(\mathbf{z}_i)}_{a_i} + \underbrace{V_{t+1}(\mathbf{x}'_i) - \mathbb{E}[V_{t+1}(\mathbf{x}') \mid\mathbf{z}_i]}_{b_i} + \underbrace{\mathbb{E}[V_{t+1}(\mathbf{x}') - V^*_{t+1}(\mathbf{x}') \mid\mathbf{z}_i]}_{c_i},
\end{aligned} η t , i := y t , i − Q ∗ ( z i ) = a i r i − r ˉ t ( z i ) + b i V t + 1 ( x i ′ ) − E [ V t + 1 ( x ′ ) ∣ z i ] + c i E [ V t + 1 ( x ′ ) − V t + 1 ∗ ( x ′ ) ∣ z i ] ,
as noise with mean zero, and Proposition 3 treats the errors of different targets as independent. For t < T − 1 t < T - 1 t < T − 1 and under the following assumption, the mean is approximately zero and the errors of the targets of a time step have covariance D t + S t D_t + S_t D t + S t , with D t D_t D t diagonal, from the reward and the next state, and S t S_t S t a kernel, from the error of the next estimate. HGPQ’s variances (8) estimate D t D_t D t . This derivation concerns the choice of variances only and is not needed for Theorem 1, which holds for any variances that satisfy Assumption 2(v).
Assumption 1 (Target variances). At a time step t < T − 1 t < T - 1 t < T − 1 , the following hold for every stored transition ( z i , r i , x i ′ ) (\mathbf{z}_i, r_i, \mathbf{x}'_i) ( z i , r i , x i ′ ) .
(i) Given the data of later time steps, μ t + 1 \mu_{t+1} μ t + 1 is fixed and Q t + 1 ∗ = μ t + 1 + ε Q^{*}_{t+1}=\mu_{t+1}+\varepsilon Q t + 1 ∗ = μ t + 1 + ε with ε ∼ G P ( 0 , Σ t + 1 ) \varepsilon\sim\mathcal{GP}(0,\Sigma_{t+1}) ε ∼ G P ( 0 , Σ t + 1 ) , as if the optimal Q Q Q -function were drawn from the posterior.
(ii) Given z i z_i z i , the error ε \varepsilon ε is independent of the process draw ( r i , x i ′ ) (r_i,\mathbf{x}'_i) ( r i , x i ′ ) , and r i r_i r i is uncorrelated with V t + 1 ( x i ′ ) V_{t+1}(\mathbf{x}'_i) V t + 1 ( x i ′ ) .
(iii) For every next state x ′ \mathbf{x}' x ′ , μ t + 1 ( x ′ , ⋅ ) \mu_{t+1}(\mathbf{x}',\cdot) μ t + 1 ( x ′ , ⋅ ) has a unique maximiser u ∗ ( x ′ ) \mathbf{u}^{*}(\mathbf{x}') u ∗ ( x ′ ) on U \mathcal{U} U with quadratic growth, μ t + 1 ( x ′ , u ∗ ( x ′ ) ) − μ t + 1 ( x ′ , u ) ≥ ϱ ∥ u − u ∗ ( x ′ ) ∥ 2 \mu_{t+1}(\mathbf{x}',\mathbf{u}^{*}(\mathbf{x}'))-\mu_{t+1}(\mathbf{x}',\mathbf{u})\geq\varrho\lVert\mathbf{u}-\mathbf{u}^{*}(\mathbf{x}')\rVert^{2} μ t + 1 ( x ′ , u ∗ ( x ′ )) − μ t + 1 ( x ′ , u ) ≥ ϱ ∥ u − u ∗ ( x ′ ) ∥ 2 for all u ∈ U \mathbf{u}\in\mathcal{U} u ∈ U and some ϱ > 0 \varrho>0 ϱ > 0 , and ε ( x ′ , ⋅ ) \varepsilon(\mathbf{x}',\cdot) ε ( x ′ , ⋅ ) is Lipschitz on U \mathcal{U} U with constant G ( x ′ ) G(\mathbf{x}') G ( x ′ ) .
(iv) The clipping in (3) is inactive, so V t + 1 ( x ′ ) = max u μ t + 1 ( x ′ , u ) V_{t+1}(\mathbf{x}')=\max_{\mathbf{u}}\mu_{t+1}(\mathbf{x}',\mathbf{u}) V t + 1 ( x ′ ) = max u μ t + 1 ( x ′ , u ) .
Mean of the error. The reward and next-state parts have mean zero by definition, and the error of the next estimate has mean zero to first order. Expectations are over the process draw of ( r i , x i ′ ) (r_i,\mathbf{x}'_i) ( r i , x i ′ ) given z i z_i z i and over ε \varepsilon ε . By the definitions of r ˉ t \bar{r}_t r ˉ t and P t P_t P t , E [ a i ] = E [ b i ] = 0 \mathbb{E}[a_i]=\mathbb{E}[b_i]=0 E [ a i ] = E [ b i ] = 0 . For c i c_i c i , fix x ′ \mathbf{x}' x ′ , write u ∗ : = u ∗ ( x ′ ) \mathbf{u}^{*}:=\mathbf{u}^{*}(\mathbf{x}') u ∗ := u ∗ ( x ′ ) and let
R ( x ′ ) : = max u ( μ t + 1 ( x ′ , u ) − μ t + 1 ( x ′ , u ∗ ) + ε ( x ′ , u ) − ε ( x ′ , u ∗ ) ) R(\mathbf{x}'):=\max_{\mathbf{u}}\left(\mu_{t+1}(\mathbf{x}',\mathbf{u})-\mu_{t+1}(\mathbf{x}',\mathbf{u}^{*})+\varepsilon(\mathbf{x}',\mathbf{u})-\varepsilon(\mathbf{x}',\mathbf{u}^{*})\right) R ( x ′ ) := u max ( μ t + 1 ( x ′ , u ) − μ t + 1 ( x ′ , u ∗ ) + ε ( x ′ , u ) − ε ( x ′ , u ∗ ) )
be the amount by which the maximum of μ t + 1 + ε \mu_{t+1}+\varepsilon μ t + 1 + ε exceeds its value at u ∗ \mathbf{u}^{*} u ∗ . By (i) and (iv), V t + 1 ∗ ( x ′ ) − V t + 1 ( x ′ ) = ε ( x ′ , u ∗ ) + R ( x ′ ) V^{*}_{t+1}(\mathbf{x}')-V_{t+1}(\mathbf{x}')=\varepsilon(\mathbf{x}',\mathbf{u}^{*})+R(\mathbf{x}') V t + 1 ∗ ( x ′ ) − V t + 1 ( x ′ ) = ε ( x ′ , u ∗ ) + R ( x ′ ) , and 0 ≤ R ( x ′ ) ≤ G ( x ′ ) 2 / ( 4 ϱ ) 0\leq R(\mathbf{x}')\leq G(\mathbf{x}')^{2}/(4\varrho) 0 ≤ R ( x ′ ) ≤ G ( x ′ ) 2 / ( 4 ϱ ) . The lower bound follows from u = u ∗ \mathbf{u}=\mathbf{u}^{*} u = u ∗ , and the upper bound from (iii), since each term of the maximum is at most G ( x ′ ) s − ϱ s 2 G(\mathbf{x}')s-\varrho s^{2} G ( x ′ ) s − ϱ s 2 with s : = ∥ u − u ∗ ∥ s:=\lVert\mathbf{u}-\mathbf{u}^{*}\rVert s := ∥ u − u ∗ ∥ . The remainder is quadratic in ε \varepsilon ε , so to first order
c i ≈ − E [ ε ( x ′ , u ∗ ( x ′ ) ) ∣ z i ] , E [ c i ] ≈ 0 , (14) c_i\approx-\mathbb{E}\left[\varepsilon(\mathbf{x}',\mathbf{u}^{*}(\mathbf{x}'))\mid z_i\right],\qquad\mathbb{E}[c_i]\approx0, \tag*{(14)} c i ≈ − E [ ε ( x ′ , u ∗ ( x ′ )) ∣ z i ] , E [ c i ] ≈ 0 , (14)
and E [ η t , i ] ≈ 0 \mathbb{E}[\eta_{t,i}]\approx0 E [ η t , i ] ≈ 0 . Since R ≥ 0 R\geq0 R ≥ 0 , the neglected remainder makes the target underestimate the optimal value on average, by at most E [ G ( x ′ ) 2 ] / ( 4 ϱ ) \mathbb{E}[G(\mathbf{x}')^{2}]/(4\varrho) E [ G ( x ′ ) 2 ] / ( 4 ϱ ) . Condition (iii) fails when the maximiser lies at a corner of a bang-bang input set, as on the LMDP with inputs { − 1 , 1 } \{-1,1\} { − 1 , 1 } , where the expansion (14) does not apply.
Covariance of the errors. The reward and next-state parts are independent between targets, and the error of the next estimate is shared by targets whose next states are close. Let i i i and j j j be transitions of time step t t t , with i = j i=j i = j allowed. By Assumption 1(ii), c j c_j c j depends on ε \varepsilon ε alone, which is independent of the process draws, and a i + b i a_i+b_i a i + b i has mean zero given the inputs, so Cov ( a i + b i , c j ) = 0 \operatorname{Cov}(a_i+b_i,c_j)=0 Cov ( a i + b i , c j ) = 0 . The process draws of different transitions are independent given their inputs, so Cov ( a i + b i , a j + b j ) \operatorname{Cov}(a_i+b_i,a_j+b_j) Cov ( a i + b i , a j + b j ) vanishes for i ≠ j i\ne j i = j and equals Var ( r i ∣ z i ) + Var ( V t + 1 ( x ′ ) ∣ z i ) \operatorname{Var}(r_i\mid z_i)+\operatorname{Var}(V_{t+1}(\mathbf{x}')\mid z_i) Var ( r i ∣ z i ) + Var ( V t + 1 ( x ′ ) ∣ z i ) for i = j i=j i = j , by (ii). The terms c i c_i c i and c j c_j c j are averages of the same error ε \varepsilon ε , and by (14)
Cov ( c i , c j ) ≈ S t ( z i , z j ) : = ∬ Σ t + 1 ( x ′ , u ∗ ( x ′ ) ) , ( x ′ ′ , u ∗ ( x ′ ′ ) ) ) P t ( d x ′ ∣ z i ) P t ( d x ′ ′ ∣ z j ) , \operatorname{Cov}(c_i,c_j)\approx S_t(z_i,z_j):=\iint\Sigma_{t+1}(\mathbf{x}',\mathbf{u}^{*}(\mathbf{x}')),\left(\mathbf{x}'',\mathbf{u}^{*}(\mathbf{x}'')\right))P_t(\mathrm{d}\mathbf{x}'\mid z_i)P_t(\mathrm{d}\mathbf{x}''\mid z_j), Cov ( c i , c j ) ≈ S t ( z i , z j ) := ∬ Σ t + 1 ( x ′ , u ∗ ( x ′ )) , ( x ′′ , u ∗ ( x ′′ ) ) ) P t ( d x ′ ∣ z i ) P t ( d x ′′ ∣ z j ) ,
a positive semi-definite kernel on the inputs. By ∣ Σ t + 1 ( z ′ , z ′ ′ ) ∣ ≤ σ t + 1 ( z ′ ) σ t + 1 ( z ′ ′ ) \lvert\Sigma_{t+1}(\mathbf{z}',\mathbf{z}'')\rvert\leq\sigma_{t+1}(\mathbf{z}')\sigma_{t+1}(\mathbf{z}'') ∣ Σ t + 1 ( z ′ , z ′′ )∣ ≤ σ t + 1 ( z ′ ) σ t + 1 ( z ′′ ) and Jensen’s inequality, S t ( z i , z i ) ≤ E [ σ t + 1 2 ( x ′ , u ∗ ( x ′ ) ) ∣ z i ] S_t(z_i,z_i)\leq\mathbb{E}[\sigma_{t+1}^{2}(\mathbf{x}',\mathbf{u}^{*}(\mathbf{x}'))\mid z_i] S t ( z i , z i ) ≤ E [ σ t + 1 2 ( x ′ , u ∗ ( x ′ )) ∣ z i ] , with equality when the next state is a deterministic function of z i z_i z i . Hence
Cov ( η t ) ≈ D t + S t , D t : = diag ( Var ( r i ∣ z i ) + Var ( V t + 1 ( x ′ ) ∣ z i ) ) i , \operatorname{Cov}(\boldsymbol{\eta}_t)\approx D_t+S_t,\qquad D_t:=\operatorname{diag}\left(\operatorname{Var}(r_i\mid z_i)+\operatorname{Var}(V_{t+1}(\mathbf{x}')\mid z_i)\right)_i, Cov ( η t ) ≈ D t + S t , D t := diag ( Var ( r i ∣ z i ) + Var ( V t + 1 ( x ′ ) ∣ z i ) ) i ,
with S t : = ( S t ( z i , z j ) ) i j S_t:=(S_t(z_i,z_j))_{ij} S t := ( S t ( z i , z j ) ) ij . The entry S t ( z i , z j ) S_t(z_i,z_j) S t ( z i , z j ) is close to S t ( z i , z i ) S_t(z_i,z_i) S t ( z i , z i ) when the next states of z i z_i z i and z j z_j z j are close compared with the lengthscales of Σ t + 1 \Sigma_{t+1} Σ t + 1 , so targets at nearby inputs share most of this error.
Consequence for the variances. Under this model the posterior mean is
κ ⊤ ( K + S t + D t ) − 1 y , \boldsymbol{\kappa}^{\top}(K+S_t+D_t)^{-1}\mathbf{y}, κ ⊤ ( K + S t + D t ) − 1 y ,
in which S t S_t S t enters as a second kernel on the data, a smooth error that the regression cannot separate from Q t ∗ Q_t^* Q t ∗ by its targets alone. Replacing S t S_t S t by its diagonal, as a variance σ t + 1 2 ( x i ′ , u i ∗ ) \sigma_{t+1}^2(x_i',u_i^*) σ t + 1 2 ( x i ′ , u i ∗ ) added to each target’s noise, would treat this shared error as independent and averaged away, which it is not. Proposition 3 therefore applies to D t D_t D t alone. HGPQ sets Λ t \Lambda_t Λ t to an estimate of D t D_t D t , namely σ r 2 + ω t ( z i ) \sigma_r^2+\omega_t(z_i) σ r 2 + ω t ( z i ) (§ 3.3 ), which gives (8) , and leaves the shared error as a bias of the targets, which vanishes as μ t + 1 → Q t + 1 ∗ \mu_{t+1}\to Q_{t+1}^* μ t + 1 → Q t + 1 ∗ . Where V t + 1 V_{t+1} V t + 1 has kinks, at states where the maximiser of μ t + 1 \mu_{t+1} μ t + 1 switches, the smooth expansion (14) does not hold, part of the error of the next estimate behaves as independent error, and the leave-one-out estimate includes it in ω t \omega_t ω t . Appendix G compares this choice with adding σ t + 1 2 ( x i ′ , u i ∗ ) \sigma_{t+1}^2(x_i',u_i^*) σ t + 1 2 ( x i ′ , u i ∗ ) to it, with a tuned constant plus σ t + 1 2 \sigma_{t+1}^2 σ t + 1 2 , and with the full covariance S t S_t S t evaluated at the realised next states.
At t = T − 1 t=T-1 t = T − 1 the next value is the terminal value V T V_T V T of § 3.1 , with V T ∗ = r ˉ T V_T^*=\bar r_T V T ∗ = r ˉ T and no maximisation. Then b i b_i b i is the spread of V T ( x ′ ) V_T(x') V T ( x ′ ) over next states, which ω T − 1 ( z i ) \omega_{T-1}(z_i) ω T − 1 ( z i ) absorbs together with any reward noise beyond σ r 2 \sigma_r^2 σ r 2 . The term c i c_i c i vanishes when r ˉ T \bar r_T r ˉ T is known, and also when the measured terminal reward is used, since E [ r T ∣ z i ] = E [ r ˉ T ( x ′ ) ∣ z i ] \mathbb{E}[r_T\mid z_i]=\mathbb{E}[\bar r_T(x')\mid z_i] E [ r T ∣ z i ] = E [ r ˉ T ( x ′ ) ∣ z i ] , and the measurement noise then enters b i b_i b i . With a terminal GP, c i c_i c i is the shared error of that GP and is treated as above. Without a terminal reward, b i = c i = 0 b_i=c_i=0 b i = c i = 0 .
Convergence in function space
This subsection proves Theorem 1 in a more general form, in which each target has its own variance and all variances may grow with the number of episodes by a deterministic schedule. With one variance per time step and no schedule, each backward step is the regression step of kernel value iteration (Yang et al., 2020).
The argument has three steps. The first bounds the error of one regression step by the posterior standard deviation times a width, uniformly over the candidate value functions from which the targets are built. The second shows that coverage makes the posterior standard deviation shrink at a known rate on each region. The third adds the errors of the time steps, backwards from the last. The paragraphs below fix the notation, Appendix A.4.1 states the assumptions, and the lemmas of Appendix A.4.3 carry out the three steps.
Standing assumptions. The set X \mathcal{X} X is compact, U \mathcal{U} U is a closed box with sides of positive length, ∥ ⋅ ∥ \lVert\cdot\rVert ∥ ⋅ ∥ is the Euclidean norm on Z = X × U ⊂ R d \mathcal{Z}=\mathcal{X}\times\mathcal{U}\subset\mathbb{R}^d Z = X × U ⊂ R d with d : = d x + d u d:=d_x+d_u d := d x + d u , and the kernel κ \kappa κ is continuous on Z × Z \mathcal{Z}\times\mathcal{Z} Z × Z . Hence κ max : = sup z ∈ Z κ ( z , z ) < ∞ \kappa_{\max}:=\sup_{z\in\mathcal{Z}}\kappa(z,z)<\infty κ m a x := sup z ∈ Z κ ( z , z ) < ∞ , the reproducing kernel Hilbert space (RKHS) H κ \mathcal{H}_\kappa H κ is separable and consists of continuous functions, and its balls are relatively compact in the supremum norm on Z \mathcal{Z} Z . The reproducing property is g ( z ) = ⟨ g , κ ( ⋅ , z ) ⟩ κ g(z)=\langle g,\kappa(\cdot,z)\rangle_\kappa g ( z ) = ⟨ g , κ ( ⋅ , z ) ⟩ κ .
Episodes and information. The proof tracks what the learner knows when it chooses each input. In episode i = 1 , 2 , … i=1,2,\ldots i = 1 , 2 , … , time step t t t produces a pair z t , i = ( x t , i , u t , i ) z_{t,i}=(x_{t,i},u_{t,i}) z t , i = ( x t , i , u t , i ) , a reward r t , i r_{t,i} r t , i and a next state x t + 1 , i x_{t+1,i} x t + 1 , i . Let F i \mathcal{F}_i F i be the σ \sigma σ -algebra generated by everything that the learner has observed or sampled by the end of episode i i i , including its exploration noise, and let G t , i \mathcal{G}_{t,i} G t , i be generated by F i − 1 \mathcal{F}_{i-1} F i − 1 and everything in episode i i i up to and including the choice of u t , i u_{t,i} u t , i . Then z t , i z_{t,i} z t , i is G t , i \mathcal{G}_{t,i} G t , i -measurable and ( r t , i , x t + 1 , i ) (r_{t,i},x_{t+1,i}) ( r t , i , x t + 1 , i ) is F i \mathcal{F}_i F i -measurable, hence G t , i + 1 \mathcal{G}_{t,i+1} G t , i + 1 -measurable.
Simplifications. As in § 4 , rewards lie in [ 0 , 1 ] [0,1] [ 0 , 1 ] , so values at time step t t t lie in [ 0 , T − t ] [0,T-t] [ 0 , T − t ] , the maximisation over inputs is exact, the kernel is fixed, the targets are not standardised and N 0 = 0 N_0=0 N 0 = 0 , so the i i i -th transition of D t \mathcal{D}_t D t is that of episode i i i . A known or measured terminal reward is added to the reward of the last time step and rescaled with it, Q T ∗ : = 0 Q_T^* := 0 Q T ∗ := 0 , and a terminal GP is not treated.
Bellman operator. Let Π [ a , b ] \Pi_{[a,b]} Π [ a , b ] denote clipping onto [ a , b ] [a,b] [ a , b ] and ( P t V ) ( z ) : = E x ′ ∼ P t ( ⋅ ∣ z ) [ V ( x ′ ) ] (P_tV)(\mathbf{z}) := \mathbb{E}_{\mathbf{x}'\sim P_t(\cdot\mid\mathbf{z})}[V(\mathbf{x}')] ( P t V ) ( z ) := E x ′ ∼ P t ( ⋅ ∣ z ) [ V ( x ′ )] for bounded measurable V V V . For continuous g : Z → R g:\mathcal{Z}\to\mathbb{R} g : Z → R , the clipped greedy value, the Bellman operator and the targets are
V g t + 1 ( x ) : = Π [ 0 , T − t − 1 ] ( max u ∈ U g ( x , u ) ) , T g : = r ˉ t + P t V g t + 1 , V_g^{t+1}(\mathbf{x}) := \Pi_{[0,T-t-1]}\left(\max_{\mathbf{u}\in\mathcal{U}} g(\mathbf{x},\mathbf{u})\right), \qquad\mathcal{T}g := \bar r_t + P_tV_g^{t+1}, V g t + 1 ( x ) := Π [ 0 , T − t − 1 ] ( u ∈ U max g ( x , u ) ) , T g := r ˉ t + P t V g t + 1 ,
y t , i ( g ) : = r t , i + V g t + 1 ( x t + 1 , i ) . (15) y_{t,i}(g) := r_{t,i} + V_g^{t+1}(\mathbf{x}_{t+1,i}). \tag*{(15)} y t , i ( g ) := r t , i + V g t + 1 ( x t + 1 , i ) . (15)
Clipping and maximisation are 1-Lipschitz, so for continuous g g g and g ′ g' g ′ and every x ∈ X \mathbf{x}\in\mathcal{X} x ∈ X ,
∣ V g t + 1 ( x ) − V g ′ t + 1 ( x ) ∣ ≤ sup u ∈ U ∣ g ( x , u ) − g ′ ( x , u ) ∣ . (16) \left|V_g^{t+1}(\mathbf{x})-V_{g'}^{t+1}(\mathbf{x})\right| \le\sup_{\mathbf{u}\in\mathcal{U}}\left|g(\mathbf{x},\mathbf{u})-g'(\mathbf{x},\mathbf{u})\right|. \tag*{(16)} V g t + 1 ( x ) − V g ′ t + 1 ( x ) ≤ u ∈ U sup ∣ g ( x , u ) − g ′ ( x , u ) ∣ . (16)
Variances and schedule. The target of transition i i i at time step t t t has a base variance λ t , i > 0 \lambda_{t,i}>0 λ t , i > 0 . For a schedule exponent ζ ∈ [ 0 , 1 ) \zeta\in[0,1) ζ ∈ [ 0 , 1 ) and χ n : = n ζ \chi_n:=n^\zeta χ n := n ζ , the GP of time step t t t after n n n episodes gives this target the variance χ n λ t , i \chi_n\lambda_{t,i} χ n λ t , i . We write
Λ t , n : = χ n diag ( λ t , 1 , … , λ t , n ) , n ˉ : = n / χ n = n 1 − ζ , \Lambda_{t,n}:=\chi_n\operatorname{diag}(\lambda_{t,1},\ldots,\lambda_{t,n}), \qquad\bar n:=n/\chi_n=n^{1-\zeta}, Λ t , n := χ n diag ( λ t , 1 , … , λ t , n ) , n ˉ := n / χ n = n 1 − ζ ,
and call n ˉ \bar n n ˉ the effective number of episodes. The base variances in force after n n n episodes may depend on n n n , which is not written. Algorithm 1 uses ζ = 0 \zeta=0 ζ = 0 .
Posterior. After n n n episodes, let K t , n : = [ κ ( z t , i , z t , j ) ] i , j ≤ n K_{t,n}:=[\kappa(\mathbf{z}_{t,i},\mathbf{z}_{t,j})]_{i,j\le n} K t , n := [ κ ( z t , i , z t , j ) ] i , j ≤ n , κ t , n ( z ) : = ( κ ( z t , i , z ) ) i ≤ n \boldsymbol{\kappa}_{t,n}(\mathbf{z}):=(\kappa(\mathbf{z}_{t,i},\mathbf{z}))_{i\le n} κ t , n ( z ) := ( κ ( z t , i , z ) ) i ≤ n and y t ( g ) : = ( y t , i ( g ) ) i ≤ n \mathbf{y}_t(g):=(y_{t,i}(g))_{i\le n} y t ( g ) := ( y t , i ( g ) ) i ≤ n . For targets y ∈ R n \mathbf{y}\in\mathbb{R}^n y ∈ R n , the posterior mean and variance at time step t t t are
m t , n [ y ] ( z ) : = κ t , n ( z ) T ( K t , n + Λ t , n ) − 1 y , m_{t,n}[\mathbf{y}](\mathbf{z}):=\boldsymbol{\kappa}_{t,n}(\mathbf{z})^\mathsf{T}(K_{t,n}+\Lambda_{t,n})^{-1}\mathbf{y}, m t , n [ y ] ( z ) := κ t , n ( z ) T ( K t , n + Λ t , n ) − 1 y ,
σ t , n 2 ( z ) : = κ ( z , z ) − κ t , n ( z ) T ( K t , n + Λ t , n ) − 1 κ t , n ( z ) . (17) \sigma_{t,n}^2(\mathbf{z}):=\kappa(\mathbf{z},\mathbf{z})-\boldsymbol{\kappa}_{t,n}(\mathbf{z})^\mathsf{T}(K_{t,n}+\Lambda_{t,n})^{-1}\boldsymbol{\kappa}_{t,n}(\mathbf{z}). \tag*{(17)} σ t , n 2 ( z ) := κ ( z , z ) − κ t , n ( z ) T ( K t , n + Λ t , n ) − 1 κ t , n ( z ) . (17)
With exact maximisation, Algorithm 1 sets μ T n ≡ 0 \mu_T^n\equiv0 μ T n ≡ 0 after episode n n n and computes, for t = T − 1 , … , 0 t=T-1,\ldots,0 t = T − 1 , … , 0 ,
μ t n : = m t , n [ y t ( μ t + 1 n ) ] , (18) \mu_t^n:=m_{t,n}[\mathbf{y}_t(\mu_{t+1}^n)], \tag*{(18)} μ t n := m t , n [ y t ( μ t + 1 n )] , (18)
a finite combination of kernel functions and hence continuous. At t = T − 1 t=T-1 t = T − 1 the greedy value is clipped onto [ 0 , 0 ] [0,0] [ 0 , 0 ] , so the target is the reward alone. The error is
e t n ( z ) : = ∣ μ t n ( z ) − Q t ∗ ( z ) ∣ , e T n = 0. e_t^n(\mathbf{z}):=\left|\mu_t^n(\mathbf{z})-Q_t^*(\mathbf{z})\right|,\qquad e_T^n=0. e t n ( z ) := ∣ μ t n ( z ) − Q t ∗ ( z ) ∣ , e T n = 0.
Assumptions
Sub-Gaussian noise and regions. The noise of the targets is assumed sub-Gaussian given the past. A random variable η \eta η is conditionally s s s -sub-Gaussian given a σ \sigma σ -algebra G \mathcal{G} G , for a G \mathcal{G} G -measurable s ≥ 0 s\ge0 s ≥ 0 , if E [ exp ( a η ) ∣ G ] ≤ exp ( a 2 s 2 / 2 ) \mathbb{E}[\exp(a\eta)\mid\mathcal{G}]\le\exp(a^2s^2/2) E [ exp ( a η ) ∣ G ] ≤ exp ( a 2 s 2 /2 ) almost surely for every real a a a . Then E [ η ∣ G ] = 0 \mathbb{E}[\eta\mid\mathcal{G}]=0 E [ η ∣ G ] = 0 , and η / b \eta/b η / b is conditionally ( s / b ) (s/b) ( s / b ) -sub-Gaussian for every G \mathcal{G} G -measurable b > 0 b>0 b > 0 . The error is bounded uniformly on regions Z t : = X t × U \mathcal{Z}_t:=\mathcal{X}_t\times\mathcal{U} Z t := X t × U , with closed boxes X t ⊆ X \mathcal{X}_t\subseteq\mathcal{X} X t ⊆ X whose sides have positive length.
Definition 4 (Local approximation property). The kernel κ \kappa κ has the local approximation property on a box Z t \mathcal{Z}_t Z t with exponent q > 0 q > 0 q > 0 if there are constants L κ ≥ 0 L_\kappa\ge0 L κ ≥ 0 , h κ > 0 h_\kappa> 0 h κ > 0 and c κ ≥ 1 c_\kappa\ge1 c κ ≥ 1 with the following property. For every h ≤ h κ h \le h_\kappa h ≤ h κ , every finite set S ⊂ Z t S \subset\mathcal{Z}_t S ⊂ Z t with sup z ∈ Z t min z ′ ∈ S ∥ z − z ′ ∥ ≤ h \sup_{z\in\mathcal{Z}_t} \min_{z'\in S} \lVert z-z'\rVert\le h sup z ∈ Z t min z ′ ∈ S ∥ z − z ′ ∥ ≤ h , and every z ∈ Z t z \in\mathcal{Z}_t z ∈ Z t , there are weights ( w z ′ ) z ′ ∈ S (w_{z'})_{z'\in S} ( w z ′ ) z ′ ∈ S with ∑ z ′ ∣ w z ′ ∣ ≤ c κ \sum_{z'} |w_{z'}| \le c_\kappa ∑ z ′ ∣ w z ′ ∣ ≤ c κ such that
∥ κ ( ⋅ , z ) − ∑ z ′ ∈ S w z ′ κ ( ⋅ , z ′ ) ∥ κ 2 ≤ L κ h 2 q . \left\lVert\kappa(\cdot,z)-\sum_{z'\in S}w_{z'}\kappa(\cdot,z')\right\rVert_\kappa^2 \le L_\kappa h^{2q}. κ ( ⋅ , z ) − z ′ ∈ S ∑ w z ′ κ ( ⋅ , z ′ ) κ 2 ≤ L κ h 2 q .
If κ ( z , z ) + κ ( z ′ , z ′ ) − 2 κ ( z , z ′ ) ≤ L κ ∥ z − z ′ ∥ 2 q \kappa(z,z)+\kappa(z',z')-2\kappa(z,z')\le L_\kappa\lVert z-z'\rVert^{2q} κ ( z , z ) + κ ( z ′ , z ′ ) − 2 κ ( z , z ′ ) ≤ L κ ∥ z − z ′ ∥ 2 q on Z t \mathcal{Z}_t Z t , the property holds with exponent q q q and c κ = 1 c_\kappa=1 c κ = 1 , by placing all of the weight on a nearest point of S S S . This Hölder condition holds with q = 1 q=1 q = 1 on bounded sets for a Matérn kernel with ν > 1 \nu>1 ν > 1 and for the squared-exponential kernel.
Assumption 2. There are constants B t < ∞ B_t<\infty B t < ∞ , ρ t > 0 \rho_t>0 ρ t > 0 , 0 < λ − ≤ λ + 0<\lambda_-\le\lambda_+ 0 < λ − ≤ λ + and ς t > 0 \varsigma_t>0 ς t > 0 , none of which depends on the episode, such that the following conditions hold for every time step t t t , every n n n and every episode i ≤ n i\le n i ≤ n .
(i) Markov property. There is a probability kernel P t P_t P t from Z t \mathcal{Z}_t Z t to [ 0 , 1 ] × X [0,1]\times\mathcal{X} [ 0 , 1 ] × X , under which the reward has mean r ˉ t ( z ) \bar r_t(z) r ˉ t ( z ) and the next state has distribution P t ( ⋅ ∣ z ) P_t(\cdot\mid z) P t ( ⋅ ∣ z ) , such that P ( ( r t , i , x t + 1 , i ) ∈ A ∣ G t , i ) = P t ( A ∣ z t , i ) \mathbb{P}((r_{t,i},x_{t+1,i})\in A\mid\mathcal{G}_{t,i})=P_t(A\mid z_{t,i}) P (( r t , i , x t + 1 , i ) ∈ A ∣ G t , i ) = P t ( A ∣ z t , i ) almost surely for every Borel set A A A .
(ii) Completeness. For every measurable V : X → [ 0 , T − t − 1 ] V:\mathcal{X}\to[0,T-t-1] V : X → [ 0 , T − t − 1 ] , the backup r ˉ t + P t V \bar r_t+P_tV r ˉ t + P t V lies in H κ \mathcal{H}_\kappa H κ and has RKHS norm at most B t B_t B t .
(iii) Kernel. On every Z t \mathcal{Z}_t Z t , the kernel κ \kappa κ has the local approximation property of Definition 4 , with an exponent q > 0 q>0 q > 0 and constants L κ L_\kappa L κ , h κ h_\kappa h κ and c κ c_\kappa c κ that do not depend on t t t .
(iv) Coverage and closure. For every Borel set E ⊆ Z t E\subseteq\mathcal{Z}_t E ⊆ Z t , with volume Leb ( E ) \operatorname{Leb}(E) Leb ( E ) , P ( z t , i ∈ E ∣ F i − 1 ) ≥ ρ t Leb ( E ) \mathbb{P}(z_{t,i}\in E\mid\mathcal{F}_{i-1})\ge\rho_t\operatorname{Leb}(E) P ( z t , i ∈ E ∣ F i − 1 ) ≥ ρ t Leb ( E ) almost surely. If t ≤ T − 2 t\le T-2 t ≤ T − 2 , then P t ( X t + 1 ∣ z ) = 1 P_t(\mathcal{X}_{t+1}\mid z)=1 P t ( X t + 1 ∣ z ) = 1 for every z ∈ Z t z\in\mathcal{Z}_t z ∈ Z t .
(v) Variances. The base variance λ t , i \lambda_{t,i} λ t , i in force after n n n episodes lies in [ λ − , λ + ] [\lambda_-,\lambda_+] [ λ − , λ + ] and is G t , i \mathcal{G}_{t,i} G t , i -measurable. For every continuous g g g , the noise η t , i ( g ) : = y t , i ( g ) − ( T t g ) ( z t , i ) \eta_{t,i}(g):=y_{t,i}(g)-(T_tg)(z_{t,i}) η t , i ( g ) := y t , i ( g ) − ( T t g ) ( z t , i ) is conditionally ς t λ t , i \varsigma_t\sqrt{\lambda_{t,i}} ς t λ t , i -sub-Gaussian given G t , i \mathcal{G}_{t,i} G t , i .
Condition (i) also requires that the learner’s own randomness, such as its Thompson draws, carries no information about the next outcome. Condition (ii) concerns every bounded value function, not only V t + 1 ∗ V^*_{t+1} V t + 1 ∗ , because the targets are built from the data-dependent μ t + 1 n \mu^n_{t+1} μ t + 1 n . It is the completeness condition of kernel value iteration ((Yang et al., 2020)), the linear MDP condition of Jin et al. [32 ] for a linear kernel, and it cannot be weakened to Q t ∗ ∈ H κ Q^*_t\in\mathcal{H}_\kappa Q t ∗ ∈ H κ without losing polynomial sample complexity ([56 ] ). Coverage in (iv) holds with ρ t = ϵ ν t / Leb ( U ) \rho_t=\epsilon\nu_t/\operatorname{Leb}(\mathcal{U}) ρ t = ϵ ν t / Leb ( U ) if, given the past, the state has a density of at least ν t > 0 \nu_t>0 ν t > 0 on X t \mathcal{X}_t X t and the uniform input is chosen with a probability ϵ \epsilon ϵ that does not decay with i i i . Closure holds when the dynamics keep the states in a box X = X t \mathcal{X}=\mathcal{X}_t X = X t . Where the visited pairs lie on a lower-dimensional set, as for the pendulum’s ( sin θ , cos θ , θ ˙ ) (\sin\theta,\cos\theta,\dot\theta) ( sin θ , cos θ , θ ˙ ) or the reactor’s initial C B = C C = 0 C_B=C_C=0 C B = C C = 0 , condition (iv) holds in coordinates of that set, with d d d its dimension. Condition (v) admits a variance fixed in advance or computed from the episodes before i i i and evaluated at z t , i z_{t,i} z t , i , and excludes one re-estimated from the outcome of its own transition or from later episodes. Its sub-Gaussian part always holds with ς t = ( T − t ) / ( 2 λ − ) \varsigma_t=(T-t)/(2\sqrt{\lambda_-}) ς t = ( T − t ) / ( 2 λ − ) by Hoeffding’s lemma ([29 ] ), since by (i) the noise has conditional mean zero and lies in an interval of length T − t T-t T − t with G t , i \mathcal{G}_{t,i} G t , i -measurable endpoints.
Optimal Q Q Q -functions. If Q t + 1 ∗ Q^{*}_{t+1} Q t + 1 ∗ is continuous, which holds at t + 1 = T t+1=T t + 1 = T , then V t + 1 ∗ = max u Q t + 1 ∗ ( ⋅ , u ) V^{*}_{t+1}=\max_{u}Q^{*}_{t+1}(\cdot,u) V t + 1 ∗ = max u Q t + 1 ∗ ( ⋅ , u ) is continuous with values in [ 0 , T − t − 1 ] [0,T-t-1] [ 0 , T − t − 1 ] , so V t + 1 ∗ = V Q t + 1 ∗ V^{*}_{t+1}=V^{Q^{*}_{t+1}} V t + 1 ∗ = V Q t + 1 ∗ and the Bellman equation of § 2 reads
Q t ∗ = T t Q t + 1 ∗ . (19) Q^{*}_{t}=T_{t}Q^{*}_{t+1}. \tag*{(19)} Q t ∗ = T t Q t + 1 ∗ . (19)
By (ii), Q t ∗ ∈ H κ Q^{*}_{t}\in\mathcal{H}_{\kappa} Q t ∗ ∈ H κ with norm at most B t B_{t} B t , so it is continuous, and by backward induction (19) holds for every t ≤ T − 1 t\leq T-1 t ≤ T − 1 .
Main result
The rate, the burn-in and the variance constant depend on the kernel through Assumption 2 2 2 (iii) and on coverage through ρ t \rho_{t} ρ t .
Definition 5 (Rate, burn-in and variance constant) Let q q q , L κ L_{\kappa} L κ , h κ h_{\kappa} h κ and c κ c_{\kappa} c κ be the constants of Assumption 2 2 2 (iii). If L κ > 0 L_{\kappa}>0 L κ > 0 , let θ : = q / ( 2 q + d ) \theta:=q/(2q+d) θ := q / ( 2 q + d ) and h n : = n ˉ − 1 / ( 2 q + d ) h_{n}:=\bar{n}^{-1/(2q+d)} h n := n ˉ − 1/ ( 2 q + d ) . If L κ = 0 L_{\kappa}=0 L κ = 0 , let θ : = 1 / 2 \theta:=1/2 θ := 1/2 and h n : = h κ / d h_{n}:=h_{\kappa}/\sqrt{d} h n := h κ / d , where h κ h_{\kappa} h κ is taken to be at most d \sqrt{d} d times the shortest side of every Z t \mathcal{Z}_{t} Z t . Let a t a_{t} a t denote the longest side of Z t \mathcal{Z}_{t} Z t and M t , n : = ( 2 a t / h n ) d M_{t,n}:=(2a_{t}/h_{n})^{d} M t , n := ( 2 a t / h n ) d . For δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , the burn-in n 0 ( δ ) n_{0}(\delta) n 0 ( δ ) is the smallest integer such that, for all n ≥ n 0 ( δ ) n\geq n_{0}(\delta) n ≥ n 0 ( δ ) and all t t t , d h n ≤ h κ \sqrt{d}\,h_{n}\leq h_{\kappa} d h n ≤ h κ , every side of Z t \mathcal{Z}_{t} Z t is at least h n h_{n} h n , and
ρ t n h n d ≥ 2 d + 3 log ( 2 T M t , n n 2 / δ ) . (20) \rho_{t}nh_{n}^{d}\geq2^{d+3}\log(2TM_{t,n}n^{2}/\delta). \tag*{(20)} ρ t n h n d ≥ 2 d + 3 log ( 2 T M t , n n 2 / δ ) . (20) For λ > 0 \lambda>0 λ > 0 let
C σ , t ( λ ) : = { ( L κ d q + 2 d + 1 c κ 2 λ / ρ t ) 1 / 2 if L κ > 0 , ( 2 d + 1 d d / 2 c κ 2 λ / ( ρ t h κ d ) ) 1 / 2 if L κ = 0 , C σ , t : = C σ , t ( λ + ) . C_{\sigma,t}(\lambda):=
\begin{cases}
\left(L_{\kappa}d^{q}+2^{d+1}c_{\kappa}^{2}\lambda/\rho_{t}\right)^{1/2} & \text{if }L_{\kappa}>0,\\
\left(2^{d+1}d^{d/2}c_{\kappa}^{2}\lambda/(\rho_{t}h_{\kappa}^{d})\right)^{1/2} & \text{if }L_{\kappa}=0,
\end{cases}
\qquad C_{\sigma,t}:=C_{\sigma,t}(\lambda_{+}). C σ , t ( λ ) := { ( L κ d q + 2 d + 1 c κ 2 λ / ρ t ) 1/2 ( 2 d + 1 d d /2 c κ 2 λ / ( ρ t h κ d ) ) 1/2 if L κ > 0 , if L κ = 0 , C σ , t := C σ , t ( λ + ) . The burn-in is finite, since the first two conditions hold for all large n n n and the left-hand side of (20) grows polynomially in n n n (n h n d ≥ n 2 q / ( 2 q + d ) nh_{n}^{d}\geq n^{2q/(2q+d)} n h n d ≥ n 2 q / ( 2 q + d ) if L κ > 0 L_{\kappa}>0 L κ > 0 , and n h n d ∝ n nh_{n}^{d}\propto n n h n d ∝ n if L κ = 0 L_{\kappa}=0 L κ = 0 ) whereas the right-hand side grows logarithmically. It grows at least exponentially with d d d .
Definition 6 (Confidence width) For points z 1 , … , z n ∈ Z \mathbf{z}_{1},\ldots,\mathbf{z}_{n}\in\mathcal{Z} z 1 , … , z n ∈ Z write K n : = [ κ ( z i , z j ) ] i , j ≤ n K_{n}:=[\kappa(\mathbf{z}_{i},\mathbf{z}_{j})]_{i,j\leq n} K n := [ κ ( z i , z j ) ] i , j ≤ n , and for λ > 0 \lambda>0 λ > 0 let
γ n ( λ ) : = sup ( z 1 , … , z n ) ∈ Z n 1 2 log det ( I n + λ − 1 K n ) \gamma_{n}(\lambda):=\sup_{(\mathbf{z}_{1},\ldots,\mathbf{z}_{n})\in\mathcal{Z}^{n}}\frac{1}{2}\log\det(I_{n}+\lambda^{-1}K_{n}) γ n ( λ ) := ( z 1 , … , z n ) ∈ Z n sup 2 1 log det ( I n + λ − 1 K n ) be the maximum information gain {(citep)}(Srinivas et al., 2010). Let ( τ n ) n ≥ 1 (\tau_{n})_{n\geq1} ( τ n ) n ≥ 1 be a deterministic sequence of positive resolutions. For R ≥ 0 R\geq0 R ≥ 0 , let N n ( R ) \mathcal{N}_{n}(R) N n ( R ) be the logarithm of the smallest number of balls of radius τ n \tau_{n} τ n in the supremum norm on Z \mathcal{Z} Z , with centres in { g ∈ H κ : ∥ g ∥ κ ≤ R } \{g\in\mathcal{H}_{\kappa}:\|g\|_{\kappa}\leq R\} { g ∈ H κ : ∥ g ∥ κ ≤ R } , that cover this set. For δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , R ≥ 0 R\geq0 R ≥ 0 and an integer A ≥ 1 A\geq1 A ≥ 1 , let
β ˉ t , n ( δ ; R , A ) : = B t + 2 τ n n ˉ / λ − + ς t 2 / χ n γ n ( χ n λ − ) + N n ( R ) + log ( 2 T n 2 A / δ ) . (21) \bar{\beta}_{t,n}(\delta;R,A):=B_{t}+2\tau_{n}\sqrt{\bar{n}/\lambda_{-}}+\varsigma_{t}\sqrt{2/\chi_{n}}\sqrt{\gamma_{n}(\chi_{n}\lambda_{-})+\mathcal{N}_{n}(R)+\log(2Tn^{2}A/\delta)}. \tag*{(21)} β ˉ t , n ( δ ; R , A ) := B t + 2 τ n n ˉ / λ − + ς t 2/ χ n γ n ( χ n λ − ) + N n ( R ) + log ( 2 T n 2 A / δ ) . (21) The confidence widths are β T , n ( δ ) : = 0 \beta_{T,n}(\delta):=0 β T , n ( δ ) := 0 and β t , n ( δ ) : = β ˉ t , n ( δ ; β t + 1 , n ( δ ) , 1 ) \beta_{t,n}(\delta):=\bar{\beta}_{t,n}(\delta;\beta_{t+1,n}(\delta),1) β t , n ( δ ) := β ˉ t , n ( δ ; β t + 1 , n ( δ ) , 1 ) for t = T − 1 , … , 0 t=T-1,\ldots,0 t = T − 1 , … , 0 .
The widths are deterministic and finite. The radius R R R is that of a ball of candidate value functions, and A A A is the number of variance assignments for which the bounds hold simultaneously. Since N n ( 0 ) = 0 \mathcal{N}_{n}(0)=0 N n ( 0 ) = 0 , the width of time step T − 1 T-1 T − 1 has no covering term.
Theorem 7 (Uniform convergence, extended form of Theorem 1). Let Assumption 2 hold, let ζ ∈ [ 0 , 1 ) \zeta\in[0,1) ζ ∈ [ 0 , 1 ) and let δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) . With probability at least 1 − 2 δ 1-2\delta 1 − 2 δ , the following hold for all time steps t t t .
(a) For all n ≥ 1 n \ge1 n ≥ 1 and all z ∈ Z z \in\mathcal{Z} z ∈ Z ,
∣ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) ∣ ≤ β t , n ( δ ) σ t , n ( z ) . \left|\mu_t^n(z)-(\mathcal{T}_t\mu_{t+1}^n)(z)\right| \le\beta_{t,n}(\delta)\sigma_{t,n}(z). μ t n ( z ) − ( T t μ t + 1 n ) ( z ) ≤ β t , n ( δ ) σ t , n ( z ) . (b) For all n ≥ 1 n \ge1 n ≥ 1 and all z ∈ Z z \in\mathcal{Z} z ∈ Z , with the expectation taken over the next state alone,
e t n ( z ) ≤ β t , n ( δ ) σ t , n ( z ) + E x ′ ∼ P t ( ⋅ ∣ z ) [ sup u ∈ U e t + 1 n ( x ′ , u ) ] . e_t^n(z) \le\beta_{t,n}(\delta)\sigma_{t,n}(z)+\mathbb{E}_{x'\sim P_t(\cdot\mid z)}\left[\sup_{u\in\mathcal{U}}e_{t+1}^n(x',u)\right]. e t n ( z ) ≤ β t , n ( δ ) σ t , n ( z ) + E x ′ ∼ P t ( ⋅ ∣ z ) [ u ∈ U sup e t + 1 n ( x ′ , u ) ] . (c) For all n ≥ n 0 ( δ ) n \ge n_0(\delta) n ≥ n 0 ( δ ) ,
sup z ∈ Z t e t n ( z ) ≤ n ˉ − θ ∑ j = t T − 1 C σ , j β j , n ( δ ) . \sup_{z\in\mathcal{Z}_t}e_t^n(z)\le\bar{n}^{-\theta}\sum_{j=t}^{T-1}C_{\sigma,j}\beta_{j,n}(\delta). z ∈ Z t sup e t n ( z ) ≤ n ˉ − θ j = t ∑ T − 1 C σ , j β j , n ( δ ) . If n ˉ − θ β j , n ( δ ) → 0 \bar{n}^{-\theta}\beta_{j,n}(\delta)\to0 n ˉ − θ β j , n ( δ ) → 0 as n → ∞ n\to\infty n → ∞ for every j j j and every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , then μ t n → Q t ∗ \mu_t^n\to Q_t^* μ t n → Q t ∗ uniformly on Z t \mathcal{Z}_t Z t almost surely, for every t t t .
Part (b) shows that the Bellman backup passes errors on without amplification. Part (c) and the almost-sure statement form Theorem 1.
Proof
The proof bounds the error of a GP mean fitted to noisy targets by the posterior standard deviation times a width ([33 , 1 ] ), makes this bound uniform over a ball of candidate value functions, because the targets at time step t t t are built from the data-dependent μ t + 1 n \mu_{t+1}^n μ t + 1 n , and shows that coverage makes the posterior standard deviation decrease uniformly at the rate n ˉ − θ \bar{n}^{-\theta} n ˉ − θ , a uniform version of the local variance bounds of [35 ] . Compared with kernel value iteration ((Yang et al., 2020)), it replaces optimism by coverage and bounds the error of the estimate itself in the supremum norm.
The posterior norm. Fix points z 1 , … , z n ∈ Z z_1,\ldots,z_n\in\mathcal{Z} z 1 , … , z n ∈ Z and variances λ 1 , … , λ n > 0 \lambda_1,\ldots,\lambda_n>0 λ 1 , … , λ n > 0 , let Λ : = diag ( λ 1 , … , λ n ) \Lambda:=\operatorname{diag}(\lambda_1,\ldots,\lambda_n) Λ := diag ( λ 1 , … , λ n ) , write K K K , κ n \kappa_n κ n , m m m and σ \sigma σ for the quantities of (17) built from them, and write f ( z 1 : n ) : = ( f ( z i ) ) i ≤ n f(z_{1:n}):=(f(z_i))_{i\le n} f ( z 1 : n ) := ( f ( z i ) ) i ≤ n . The posterior norm is
∥ g ∥ Λ 2 : = ∥ g ∥ κ 2 + ∑ i ≤ n g ( z i ) 2 λ i , g ∈ H κ . \|g\|_{\Lambda}^{2}:=\|g\|_{\kappa}^{2}+\sum_{i\le n}\frac{g(z_i)^2}{\lambda_i},\qquad g\in\mathcal{H}_{\kappa}. ∥ g ∥ Λ 2 := ∥ g ∥ κ 2 + i ≤ n ∑ λ i g ( z i ) 2 , g ∈ H κ .
Lemma 8 (Posterior norm). For all f , g ∈ H κ f,g\in\mathcal{H}_{\kappa} f , g ∈ H κ , v ∈ R n v\in\mathbb{R}^n v ∈ R n and z ∈ Z z\in\mathcal{Z} z ∈ Z ,
(a) ∣ g ( z ) ∣ ≤ σ ( z ) ∥ g ∥ Λ |g(z)|\le\sigma(z)\|g\|_{\Lambda} ∣ g ( z ) ∣ ≤ σ ( z ) ∥ g ∥ Λ ,
(b) ∥ m [ v ] ∥ Λ 2 = v T ( Λ − 1 − ( K + Λ ) − 1 ) v ≤ ∥ Λ − 1 / 2 v ∥ 2 2 \|m[v]\|_{\Lambda}^{2}=v^{\mathsf{T}}\left(\Lambda^{-1}-(K+\Lambda)^{-1}\right)v\le\|\Lambda^{-1/2}v\|_2^2 ∥ m [ v ] ∥ Λ 2 = v T ( Λ − 1 − ( K + Λ ) − 1 ) v ≤ ∥ Λ − 1/2 v ∥ 2 2 ,
(c) ∥ f − m [ f ( z 1 : n ) ] ∥ Λ ≤ ∥ f ∥ κ \|f-m[f(z_{1:n})]\|_{\Lambda}\le\|f\|_{\kappa} ∥ f − m [ f ( z 1 : n )] ∥ Λ ≤ ∥ f ∥ κ ,
(d) ∥ m [ f ( z 1 : n ) ] ∥ κ ≤ ∥ f ∥ κ \|m[f(z_{1:n})]\|_{\kappa}\le\|f\|_{\kappa} ∥ m [ f ( z 1 : n )] ∥ κ ≤ ∥ f ∥ κ .
Consequently, if y = f ( z 1 : n ) + η + b y=f(z_{1:n})+\eta+b y = f ( z 1 : n ) + η + b with η , b ∈ R n \eta,b\in\mathbb{R}^n η , b ∈ R n , then
∣ m [ y ] ( z ) − f ( z ) ∣ ≤ σ ( z ) ( ∥ f ∥ κ + ∥ m [ η ] ∥ Λ + ∥ Λ − 1 / 2 b ∥ 2 ) . (22) |m[y](z)-f(z)|\le\sigma(z)\left(\|f\|_{\kappa}+\|m[\eta]\|_{\Lambda}+\|\Lambda^{-1/2}b\|_2\right). \tag*{(22)} ∣ m [ y ] ( z ) − f ( z ) ∣ ≤ σ ( z ) ( ∥ f ∥ κ + ∥ m [ η ] ∥ Λ + ∥ Λ − 1/2 b ∥ 2 ) . (22)
∥ m [ y ] ∥ κ ≤ ∥ f ∥ κ + ∥ m [ η ] ∥ Λ + ∥ Λ − 1 / 2 b ∥ 2 . (23) \|m[y]\|_{\kappa}\le\|f\|_{\kappa}+\|m[\eta]\|_{\Lambda}+\|\Lambda^{-1/2}b\|_2. \tag*{(23)} ∥ m [ y ] ∥ κ ≤ ∥ f ∥ κ + ∥ m [ η ] ∥ Λ + ∥ Λ − 1/2 b ∥ 2 . (23)
Lemma 8 reduces the error of a posterior mean at any pair to the posterior standard deviation times three norms, which become the function-norm, noise and discretisation terms of the width β t , n ( δ ) \beta_{t,n}(\delta) β t , n ( δ ) in Theorem 7 (a).
Proof Part (a). For weights w ∈ R n \mathbf{w} \in\mathbb{R}^{n} w ∈ R n , the reproducing property gives g ( z ) = ⟨ g , κ ( ⋅ , z ) − ∑ i w i κ ( ⋅ , z i ) ⟩ κ + ∑ i ( g ( z i ) / λ i ) λ i w i g(\mathbf{z}) = \left\langle g, \kappa(\cdot,\mathbf{z})-\sum_i w_i\kappa(\cdot,z_i)\right\rangle_{\kappa}+\sum_i(g(z_i)/\sqrt{\lambda_i})\sqrt{\lambda_i}w_i g ( z ) = ⟨ g , κ ( ⋅ , z ) − ∑ i w i κ ( ⋅ , z i ) ⟩ κ + ∑ i ( g ( z i ) / λ i ) λ i w i , and the Cauchy–Schwarz inequality bounds ∣ g ( z ) ∣ 2 |g(\mathbf{z})|^2 ∣ g ( z ) ∣ 2 by ∥ g ∥ Λ 2 \|g\|_{\Lambda}^2 ∥ g ∥ Λ 2 times
Φ z ( w ) : = ∥ κ ( ⋅ , z ) − ∑ i w i κ ( ⋅ , z i ) ∥ κ 2 + ∑ i λ i w i 2 = κ ( z , z ) − 2 w T κ n ( z ) + w T ( K + Λ ) w . (24) \Phi_{\mathbf{z}}(\mathbf{w}) := \left\|\kappa(\cdot,\mathbf{z})-\sum_iw_i\kappa(\cdot,z_i)\right\|_{\kappa}^2+\sum_i\lambda_iw_i^2=\kappa(\mathbf{z},\mathbf{z})-2\mathbf{w}^{\mathsf{T}}\kappa_n(\mathbf{z})+\mathbf{w}^{\mathsf{T}}(K+\Lambda)\mathbf{w}. \tag*{(24)} Φ z ( w ) := κ ( ⋅ , z ) − i ∑ w i κ ( ⋅ , z i ) κ 2 + i ∑ λ i w i 2 = κ ( z , z ) − 2 w T κ n ( z ) + w T ( K + Λ ) w . (24)
Its minimum, at w = ( K + Λ ) − 1 κ n ( z ) \mathbf{w}=(K+\Lambda)^{-1}\kappa_n(\mathbf{z}) w = ( K + Λ ) − 1 κ n ( z ) , is σ 2 ( z ) \sigma^2(\mathbf{z}) σ 2 ( z ) . Hence
∣ g ( z ) ∣ 2 ≤ σ 2 ( z ) ∥ g ∥ Λ 2 and σ 2 ( z ) ≤ Φ z ( w ) for every w ∈ R n . (25) |g(\mathbf{z})|^2\leq\sigma^2(\mathbf{z})\|g\|_{\Lambda}^2\qquad\text{and}\qquad\sigma^2(\mathbf{z})\leq\Phi_{\mathbf{z}}(\mathbf{w})\text{ for every }\mathbf{w}\in\mathbb{R}^{n}. \tag*{(25)} ∣ g ( z ) ∣ 2 ≤ σ 2 ( z ) ∥ g ∥ Λ 2 and σ 2 ( z ) ≤ Φ z ( w ) for every w ∈ R n . (25)
Parts (b) to (d) are standard facts of kernel ridge regression [33 ] .
Part (b). The mean m [ v ] = ∑ i c i κ ( ⋅ , z i ) m[\mathbf{v}]=\sum_i c_i\kappa(\cdot,z_i) m [ v ] = ∑ i c i κ ( ⋅ , z i ) is a combination of kernel functions with weights c : = ( K + Λ ) − 1 v \mathbf{c}:=(K+\Lambda)^{-1}\mathbf{v} c := ( K + Λ ) − 1 v , so its posterior norm is
∥ m [ v ] ∥ Λ 2 = c T K c + c T K Λ − 1 K c = v T ( K + Λ ) − 1 K Λ − 1 v , \|m[\mathbf{v}]\|_{\Lambda}^2=\mathbf{c}^{\mathsf{T}}K\mathbf{c}+\mathbf{c}^{\mathsf{T}}K\Lambda^{-1}K\mathbf{c}=\mathbf{v}^{\mathsf{T}}(K+\Lambda)^{-1}K\Lambda^{-1}\mathbf{v}, ∥ m [ v ] ∥ Λ 2 = c T K c + c T K Λ − 1 K c = v T ( K + Λ ) − 1 K Λ − 1 v ,
which equals the stated form. The inequality holds because ( K + Λ ) − 1 ⪰ 0 (K+\Lambda)^{-1}\succeq0 ( K + Λ ) − 1 ⪰ 0 .
Parts (c) and (d). Let m f : = m [ f ( z 1 : n ) ] m_f:=m[f(\mathbf{z}_{1:n})] m f := m [ f ( z 1 : n )] be the posterior mean of f ~ \tilde{f} f ~ observed without noise, f ~ : = f − m f \tilde{f}:=f-m_f f ~ := f − m f its residual and c : = ( K + Λ ) − 1 f ( z 1 : n ) \mathbf{c}:=(K+\Lambda)^{-1}f(\mathbf{z}_{1:n}) c := ( K + Λ ) − 1 f ( z 1 : n ) its weights. The residual at the data is f ~ ( z 1 : n ) = Λ c \tilde{f}(\mathbf{z}_{1:n})=\Lambda\mathbf{c} f ~ ( z 1 : n ) = Λ c , so
⟨ m f , g ⟩ κ = ∑ i c i g ( z i ) = ∑ i f ~ ( z i ) g ( z i ) λ i for every g ∈ H κ . (26) \langle m_f,g\rangle_{\kappa}=\sum_i c_i g(z_i)=\sum_i\frac{\tilde{f}(z_i)g(z_i)}{\lambda_i}\qquad\text{for every }g\in\mathcal{H}_{\kappa}. \tag*{(26)} ⟨ m f , g ⟩ κ = i ∑ c i g ( z i ) = i ∑ λ i f ~ ( z i ) g ( z i ) for every g ∈ H κ . (26)
With g = f ~ g=\tilde{f} g = f ~ , the right-hand side is the data term of ∥ f ~ ∥ Λ 2 \|\tilde{f}\|_{\Lambda}^2 ∥ f ~ ∥ Λ 2 , which gives (c),
∥ f ~ ∥ Λ 2 = ∥ f ~ ∥ κ 2 + ⟨ m f , f ~ ⟩ κ = ⟨ f , f ~ ⟩ κ ≤ ∥ f ∥ κ ∥ f ~ ∥ Λ . \|\tilde{f}\|_{\Lambda}^2=\|\tilde{f}\|_{\kappa}^2+\langle m_f,\tilde{f}\rangle_{\kappa}=\langle f,\tilde{f}\rangle_{\kappa}\leq\|f\|_{\kappa}\|\tilde{f}\|_{\Lambda}. ∥ f ~ ∥ Λ 2 = ∥ f ~ ∥ κ 2 + ⟨ m f , f ~ ⟩ κ = ⟨ f , f ~ ⟩ κ ≤ ∥ f ∥ κ ∥ f ~ ∥ Λ .
The same choice shows ⟨ m f , f ~ ⟩ κ ≥ 0 \langle m_f,\tilde{f}\rangle_{\kappa}\geq0 ⟨ m f , f ~ ⟩ κ ≥ 0 , which gives (d),
∥ m f ∥ κ 2 = ⟨ m f , f ⟩ κ − ⟨ m f , f ~ ⟩ κ ≤ ⟨ m f , f ⟩ κ ≤ ∥ m f ∥ κ ∥ f ∥ κ . \|m_f\|_{\kappa}^2=\langle m_f,f\rangle_{\kappa}-\langle m_f,\tilde{f}\rangle_{\kappa}\leq\langle m_f,f\rangle_{\kappa}\leq\|m_f\|_{\kappa}\|f\|_{\kappa}. ∥ m f ∥ κ 2 = ⟨ m f , f ⟩ κ − ⟨ m f , f ~ ⟩ κ ≤ ⟨ m f , f ⟩ κ ≤ ∥ m f ∥ κ ∥ f ∥ κ .
Consequences. By linearity, m [ y ] − f = m [ η ] + m [ b ] − f ~ m[\mathbf{y}]-f=m[\boldsymbol{\eta}]+m[\mathbf{b}]-\tilde{f} m [ y ] − f = m [ η ] + m [ b ] − f ~ . Part (a) applied to each term, with ∥ m [ b ] ∥ Λ ≤ ∥ Λ − 1 / 2 b ∥ 2 \|m[\mathbf{b}]\|_{\Lambda}\leq\|\Lambda^{-1/2}\mathbf{b}\|_2 ∥ m [ b ] ∥ Λ ≤ ∥ Λ − 1/2 b ∥ 2 from (b) and ∥ f ~ ∥ Λ ≤ ∥ f ∥ κ \|\tilde{f}\|_{\Lambda}\leq\|f\|_{\kappa} ∥ f ~ ∥ Λ ≤ ∥ f ∥ κ from (c), proves (22) . Similarly, (23) follows from m [ y ] = m f + m [ η ] + m [ b ] m[\mathbf{y}]=m_f+m[\boldsymbol{\eta}]+m[\mathbf{b}] m [ y ] = m f + m [ η ] + m [ b ] , part (d), ∥ ⋅ ∥ κ ≤ ∥ ⋅ ∥ Λ \|\cdot\|_{\kappa}\leq\|\cdot\|_{\Lambda} ∥ ⋅ ∥ κ ≤ ∥ ⋅ ∥ Λ and part (b).
Lemma 9 (Noise term). Let ( G i ) i ≥ 1 (\mathcal{G}_i)_{i\geq1} ( G i ) i ≥ 1 be a filtration and let λ min > 0 \lambda_{\min}>0 λ m i n > 0 and ς > 0 \varsigma>0 ς > 0 be constants. For i ≤ n i\leq n i ≤ n , let z i z_i z i and λ i ≥ λ min \lambda_i\geq\lambda_{\min} λ i ≥ λ m i n be G i \mathcal{G}_i G i -measurable, and let η i \eta_i η i be G i + 1 \mathcal{G}_{i+1} G i + 1 -measurable and conditionally ς λ i \varsigma\sqrt{\lambda_i} ς λ i -sub-Gaussian given G i \mathcal{G}_i G i . With probability at least 1 − δ 1-\delta 1 − δ ,
∥ m [ η 1 : n ] ∥ Λ ≤ ς 2 γ n ( λ min ) + 2 log ( 1 / δ ) . \|m[\eta_{1:n}]\|_{\Lambda}\leq\varsigma\sqrt{2\gamma_n(\lambda_{\min})+2\log(1/\delta)}. ∥ m [ η 1 : n ] ∥ Λ ≤ ς 2 γ n ( λ m i n ) + 2 log ( 1/ δ ) .
Lemma 9 supplies the noise term of the width β t , n ( δ ) \beta_{t,n}(\delta) β t , n ( δ ) in Theorem 7(a).
Proof. The proof rescales each noise term by its standard deviation and applies a self-normalised bound. Let η ~ i : = η i / λ i \widetilde{\eta}_i := \eta_i/\sqrt{\lambda_i} η i := η i / λ i , which is conditionally ς \varsigma ς -sub-Gaussian given G i \mathcal{G}_i G i because λ i \lambda_i λ i is G i \mathcal{G}_i G i -measurable, and let K ~ : = Λ − 1 / 2 K Λ − 1 / 2 \widetilde{K} := \Lambda^{-1/2}K\Lambda^{-1/2} K := Λ − 1/2 K Λ − 1/2 . With the features ϕ i : = κ ( ⋅ , z i ) / λ i \phi_i := \kappa(\cdot,z_i)/\sqrt{\lambda_i} ϕ i := κ ( ⋅ , z i ) / λ i , which are G i \mathcal{G}_i G i -measurable, and F a : = ∑ i a i ϕ i F a := \sum_i a_i\phi_i F a := ∑ i a i ϕ i , so that F ∗ F = K ~ F^*F = \widetilde{K} F ∗ F = K , Lemma 8(b) gives
∥ m [ η ] ∥ Λ 2 = η ~ ⊤ K ~ ( K ~ + I ) − 1 η ~ = ⟨ F η ~ , ( F F ∗ + i d ) − 1 F η ~ ⟩ κ . \lVert m[\eta]\rVert_{\Lambda}^{2} = \widetilde{\eta}^{\top}\widetilde{K}(\widetilde{K}+I)^{-1}\widetilde{\eta} = \langle F\widetilde{\eta},(FF^*+\mathrm{id})^{-1}F\widetilde{\eta}\rangle_{\kappa}. ∥ m [ η ] ∥ Λ 2 = η ⊤ K ( K + I ) − 1 η = ⟨ F η , ( F F ∗ + id ) − 1 F η ⟩ κ .
The self-normalised inequality of Abbasi-Yadkori et al. [1 ] in the separable Hilbert space H κ \mathcal{H}_{\kappa} H κ (Whitehouse et al., 2023, Theorem 1, with regulariser one) bounds it by 2 ς 2 log ( det ( I + K ~ ) 1 / 2 / δ ) 2\varsigma^2\log(\det(I+\widetilde{K})^{1/2}/\delta) 2 ς 2 log ( det ( I + K ) 1/2 / δ ) with probability at least 1 − δ 1-\delta 1 − δ . Finally, det ( I + K ~ ) = det ( I + K 1 / 2 Λ − 1 K 1 / 2 ) ≤ det ( I + λ min − 1 K ) ≤ e 2 γ n ( λ min ) \det(I+\widetilde{K})=\det(I+K^{1/2}\Lambda^{-1}K^{1/2})\leq\det(I+\lambda_{\min}^{-1}K)\leq e^{2\gamma_n(\lambda_{\min})} det ( I + K ) = det ( I + K 1/2 Λ − 1 K 1/2 ) ≤ det ( I + λ m i n − 1 K ) ≤ e 2 γ n ( λ m i n ) , since Λ − 1 ⪯ λ min − 1 I \Lambda^{-1}\preceq\lambda_{\min}^{-1}I Λ − 1 ⪯ λ m i n − 1 I .
Uniform concentration. A variance assignment is a family of base variances ( λ t , i ) (\lambda_{t,i}) ( λ t , i ) , for all t t t and i ≤ n i\leq n i ≤ n , that satisfies Assumption 2(v). In Theorem 7 there is one, that of the algorithm.
Lemma 10 (Uniform concentration). Let Assumption 2(i) and (ii) hold. For every n n n , let R 1 , n , … , R T , n ≥ 0 R_{1,n},\ldots,R_{T,n}\geq0 R 1 , n , … , R T , n ≥ 0 be deterministic radii, let A n ≥ 1 A_n\geq1 A n ≥ 1 be a deterministic integer, and let A n A_n A n variance assignments be given, indexed by j ≤ A n j\leq A_n j ≤ A n . Write m t , n ( j ) m_{t,n}^{(j)} m t , n ( j ) and σ t , n ( j ) \sigma_{t,n}^{(j)} σ t , n ( j ) for the posterior mean and standard deviation (17) with the base variances of assignment j j j . With probability at least 1 − δ 1-\delta 1 − δ , for all t t t , all n ≥ 1 n\geq1 n ≥ 1 , all j ≤ A n j\leq A_n j ≤ A n , all g ∈ H κ g\in\mathcal{H}_{\kappa} g ∈ H κ with ∥ g ∥ κ ≤ R t + 1 , n \lVert g\rVert_{\kappa}\leq R_{t+1,n} ∥ g ∥ κ ≤ R t + 1 , n and all z ∈ Z z\in\mathcal{Z} z ∈ Z ,
(a) ∣ m t , n ( j ) [ y t ( g ) ] ( z ) − ( T t g ) ( z ) ∣ ≤ β ‾ t , n ( δ ; R t + 1 , n , A n ) σ t , n ( j ) ( z ) , \left|m_{t,n}^{(j)}[y_t(g)](z)-(T_tg)(z)\right|\leq\overline{\beta}_{t,n}(\delta;R_{t+1,n},A_n)\sigma_{t,n}^{(j)}(z), m t , n ( j ) [ y t ( g )] ( z ) − ( T t g ) ( z ) ≤ β t , n ( δ ; R t + 1 , n , A n ) σ t , n ( j ) ( z ) ,
(b) ∥ m t , n ( j ) [ y t ( g ) ] ∥ κ ≤ β ‾ t , n ( δ ; R t + 1 , n , A n ) \lVert m_{t,n}^{(j)}[y_t(g)]\rVert_{\kappa}\leq\overline{\beta}_{t,n}(\delta;R_{t+1,n},A_n) ∥ m t , n ( j ) [ y t ( g )] ∥ κ ≤ β t , n ( δ ; R t + 1 , n , A n ) .
Lemma 10 gives Theorem 7(a) and the bound ∥ μ t n ∥ κ ≤ β t , n ( δ ) \lVert\mu_t^n\rVert_{\kappa}\leq\beta_{t,n}(\delta) ∥ μ t n ∥ κ ≤ β t , n ( δ ) that carries the argument from one time step to the one before it.
Proof. The proof applies Lemma 9 to every function of a finite cover of the ball and passes from the cover to the whole ball, which costs the discretisation term of the width. Fix t t t , n n n and j j j , and let R : = R t + 1 , n R:=R_{t+1,n} R := R t + 1 , n . Choose a deterministic set C \mathcal{C} C of e N n ( R ) e^{\mathcal{N}_n(R)} e N n ( R ) centres in the ball { ∥ g ∥ κ ≤ R } \{\lVert g\rVert_{\kappa}\leq R\} {∥ g ∥ κ ≤ R } that covers it at resolution τ n \tau_n τ n in the supremum norm.
For a centre g g g , y t , i ( g ) = ( T t g ) ( z t , i ) + η t , i ( g ) y_{t,i}(g)=(T_tg)(z_{t,i})+\eta_{t,i}(g) y t , i ( g ) = ( T t g ) ( z t , i ) + η t , i ( g ) . The variances χ n λ t , i ≥ χ n λ − \chi_n\lambda_{t,i}\geq\chi_n\lambda_- χ n λ t , i ≥ χ n λ − are G t , i \mathcal{G}_{t,i} G t , i -measurable, and by Assumption 2(v) η t , i ( g ) \eta_{t,i}(g) η t , i ( g ) is G t , i + 1 \mathcal{G}_{t,i+1} G t , i + 1 -measurable and conditionally ( ς t / χ n ) χ n λ t , i (\varsigma_t/\sqrt{\chi_n})\sqrt{\chi_n\lambda_{t,i}} ( ς t / χ n ) χ n λ t , i -sub-Gaussian given G t , i \mathcal{G}_{t,i} G t , i . Lemma 9 with ς = ς t / χ n \varsigma=\varsigma_t/\sqrt{\chi_n} ς = ς t / χ n , λ min = χ n λ − \lambda_{\min}=\chi_n\lambda_- λ m i n = χ n λ − and confidence level δ / ( 2 T n 2 A n ∣ C ∣ ) \delta/(2Tn^2A_n|\mathcal{C}|) δ / ( 2 T n 2 A n ∣ C ∣ ) gives
∥ m t , n ( j ) [ η t ( g ) ] ∥ Λ t , n ≤ ς t 2 χ n γ n ( χ n λ − ) + N n ( R ) + log ( 2 T n 2 A n / δ ) , (27) \lVert m_{t,n}^{(j)}[\eta_t(g)]\rVert_{\Lambda_{t,n}} \leq\varsigma_t\sqrt{\frac{2}{\chi_n}}\sqrt{\gamma_n(\chi_n\lambda_-)+\mathcal{N}_n(R)+\log(2Tn^2A_n/\delta)}, \tag*{(27)} ∥ m t , n ( j ) [ η t ( g )] ∥ Λ t , n ≤ ς t χ n 2 γ n ( χ n λ − ) + N n ( R ) + log ( 2 T n 2 A n / δ ) , (27)
with η t ( g ) : = ( η t , i ( g ) ) i ≤ n \eta_t(g):=(\eta_{t,i}(g))_{i\leq n} η t ( g ) := ( η t , i ( g ) ) i ≤ n . Since ∑ n n − 2 < 2 \sum_{n}n^{-2}<2 ∑ n n − 2 < 2 , a union bound gives (27) for every centre, assignment, n n n and t t t with probability at least 1 − δ 1-\delta 1 − δ .
For g g g in the ball, let g c ∈ C g_c\in\mathcal{C} g c ∈ C lie within τ n \tau_n τ n of g g g . Then y t ( g ) = ( ( T t g ) ( z t , i ) ) i ≤ n + η t ( g c ) + b y_t(g)=((T_tg)(z_{t,i}))_{i\leq n}+\eta_t(g_c)+b y t ( g ) = (( T t g ) ( z t , i ) ) i ≤ n + η t ( g c ) + b with b i : = ( V g t + 1 − V g c t + 1 ) ( x t + 1 , i ) − ( P t ( V g t + 1 − V g c t + 1 ) ) ( z t , i ) b_i:=(V_g^{t+1}-V_{g_c}^{t+1})(x_{t+1,i})-(P_t(V_g^{t+1}-V_{g_c}^{t+1}))(z_{t,i}) b i := ( V g t + 1 − V g c t + 1 ) ( x t + 1 , i ) − ( P t ( V g t + 1 − V g c t + 1 )) ( z t , i ) . By (16) , ∣ b i ∣ ≤ 2 τ n |b_i|\leq2\tau_n ∣ b i ∣ ≤ 2 τ n , so ∥ Λ t , n − 1 / 2 b ∥ 2 ≤ 2 τ n n / ( χ n λ − ) = 2 τ n n / λ − \lVert\Lambda_{t,n}^{-1/2}b\rVert_2\leq2\tau_n\sqrt{n/(\chi_n\lambda_-)}=2\tau_n\sqrt{n}/\lambda_- ∥ Λ t , n − 1/2 b ∥ 2 ≤ 2 τ n n / ( χ n λ − ) = 2 τ n n / λ − . With ∥ T t g ∥ κ ≤ B t \lVert T_tg\rVert_{\kappa}\leq B_t ∥ T t g ∥ κ ≤ B t by Assumption 2(ii), the three terms of (22) and (23) , with f = T t g f=T_tg f = T t g and η = η t ( g c ) \eta=\eta_t(g_c) η = η t ( g c ) , are bounded by those of (21) , which proves (a) and (b).
Lemma 11 (Variance decay). Let Assumption 2(iii) and (iv) hold. There is an event of probability at least 1 − δ 1-\delta 1 − δ , determined by the visited pairs alone, on which, for all t t t , all n ≥ n 0 ( δ ) n \ge n_0(\delta) n ≥ n 0 ( δ ) , all z ∈ Z t \mathbf{z} \in\mathcal{Z}_t z ∈ Z t and every choice of base variances in ( 0 , λ + ] (0,\lambda_+] ( 0 , λ + ] , where σ t , n \sigma_{t,n} σ t , n is computed with these base variances and the schedule, σ t , n ( z ) ≤ C σ , t n ˉ − θ \sigma_{t,n}(\mathbf{z}) \le C_{\sigma,t}\bar{n}^{-\theta} σ t , n ( z ) ≤ C σ , t n ˉ − θ .
Lemma 11 supplies the factor C σ , t n ˉ − θ C_{\sigma,t}\bar{n}^{-\theta} C σ , t n ˉ − θ in Theorem 7 (c).
Proof. The proof shows that every cell of a grid on Z t \mathcal{Z}_t Z t receives many visited pairs, and then combines kernel functions at these pairs into an approximation of κ ( ⋅ , z ) \kappa(\cdot,\mathbf{z}) κ ( ⋅ , z ) whose weights are small. Fix t t t and n ≥ n 0 ( δ ) n \ge n_0(\delta) n ≥ n 0 ( δ ) . Splitting each side of Z t \mathcal{Z}_t Z t into equal intervals of length between h n / 2 h_n/2 h n /2 and h n h_n h n partitions Z t \mathcal{Z}_t Z t into at most M t , n M_{t,n} M t , n cells of diameter at most d h n \sqrt{d}h_n d h n and volume at least ( h n / 2 ) d (h_n/2)^d ( h n /2 ) d .
For a cell, let X i X_i X i be the indicator that z t , i \mathbf{z}_{t,i} z t , i lies in it, which is F i \mathcal{F}_i F i -measurable, and let p n : = ρ t ( h n / 2 ) d p_n := \rho_t(h_n/2)^d p n := ρ t ( h n /2 ) d . By coverage, P ( X i = 1 ∣ F i − 1 ) ≥ p n \mathbb{P}(X_i=1 \mid\mathcal{F}_{i-1}) \ge p_n P ( X i = 1 ∣ F i − 1 ) ≥ p n , so E [ e − v X i ∣ F i − 1 ] ≤ exp ( − p n ( 1 − e − v ) ) \mathbb{E}[e^{-vX_i} \mid\mathcal{F}_{i-1}] \le\exp(-p_n(1-e^{-v})) E [ e − v X i ∣ F i − 1 ] ≤ exp ( − p n ( 1 − e − v )) for v > 0 v>0 v > 0 . By induction, and by Markov’s inequality with v = log 2 v=\log2 v = log 2 ,
E [ e − v ∑ i ≤ n X i ] ≤ exp ( − n p n ( 1 − e − v ) ) , \mathbb{E}\left[e^{-v\sum_{i\le n}X_i}\right]\le\exp\left(-np_n(1-e^{-v})\right), E [ e − v ∑ i ≤ n X i ] ≤ exp ( − n p n ( 1 − e − v ) ) ,
P ( ∑ i ≤ n X i ≤ n p n / 2 ) ≤ exp ( − n p n ( 1 − log 2 ) / 2 ) ≤ e − n p n / 8 . \mathbb{P}\left(\sum_{i\le n}X_i\le np_n/2\right)\le\exp\left(-np_n(1-\log2)/2\right)\le e^{-np_n/8}. P ( i ≤ n ∑ X i ≤ n p n /2 ) ≤ exp ( − n p n ( 1 − log 2 ) /2 ) ≤ e − n p n /8 .
By (20) and union bounds over the cells, t t t and n n n , every cell receives more than n p n / 2 np_n/2 n p n /2 pairs for all t t t and n ≥ n 0 ( δ ) n \ge n_0(\delta) n ≥ n 0 ( δ ) , except on an event of probability at most δ \delta δ that does not involve the variances.
On this event, let J > n p n / 2 J>np_n/2 J > n p n /2 be the smallest cell count, and choose J J J disjoint layers of visited pairs, each containing one pair of every cell. Every point of Z t \mathcal{Z}_t Z t lies within d h n ≤ h κ \sqrt{d}h_n\le h_\kappa d h n ≤ h κ of each layer. Fix z ∈ Z t \mathbf{z}\in\mathcal{Z}_t z ∈ Z t and base variances in ( 0 , λ + ] (0,\lambda_+] ( 0 , λ + ] , let w ( k ) \mathbf{w}^{(k)} w ( k ) be the weights of Definition 4 for layer k k k with h = d h n h=\sqrt{d}h_n h = d h n , and in (24) , with variances χ n λ t , i \chi_n\lambda_{t,i} χ n λ t , i , put the weight w z ′ ( k ) / J w_{\mathbf{z}'}^{(k)}/J w z ′ ( k ) / J on each pair z ′ \mathbf{z}' z ′ of layer k k k and zero elsewhere. By convexity of the squared norm, the kernel part of Φ z \Phi_{\mathbf{z}} Φ z is at most L κ d q h n 2 q L_\kappa d^q h_n^{2q} L κ d q h n 2 q . Since the layers are disjoint and ∑ z ′ ∣ w z ′ ( k ) ∣ ≤ c κ \sum_{\mathbf{z}'}|w_{\mathbf{z}'}^{(k)}|\le c_\kappa ∑ z ′ ∣ w z ′ ( k ) ∣ ≤ c κ , the noise part is at most χ n λ + ∑ k ≤ J c κ 2 / J 2 = c κ 2 χ n λ + / J \chi_n\lambda_+\sum_{k\le J}c_\kappa^2/J^2=c_\kappa^2\chi_n\lambda_+/J χ n λ + ∑ k ≤ J c κ 2 / J 2 = c κ 2 χ n λ + / J . By (25) , J > ρ t ( h n / 2 ) d n / 2 J>\rho_t(h_n/2)^dn/2 J > ρ t ( h n /2 ) d n /2 and n ˉ = n / χ n \bar{n}=n/\chi_n n ˉ = n / χ n ,
σ t , n 2 ( z ) ≤ L κ d q h n 2 q + 2 d + 1 c κ 2 λ + ρ t h n d n ˉ . \sigma_{t,n}^2(\mathbf{z})\le L_\kappa d^q h_n^{2q}+\frac{2^{d+1}c_\kappa^2\lambda_+}{\rho_t h_n^d\bar{n}}. σ t , n 2 ( z ) ≤ L κ d q h n 2 q + ρ t h n d n ˉ 2 d + 1 c κ 2 λ + .
If L κ > 0 L_\kappa>0 L κ > 0 , then h n 2 q = 1 / ( h n d n ˉ ) = n ˉ − 2 θ h_n^{2q}=1/(h_n^d\bar{n})=\bar{n}^{-2\theta} h n 2 q = 1/ ( h n d n ˉ ) = n ˉ − 2 θ . If L κ = 0 L_\kappa=0 L κ = 0 , the first term vanishes, h n d = h κ d n ˉ − d / 2 h_n^d=h_\kappa^d\bar{n}^{-d/2} h n d = h κ d n ˉ − d /2 and 2 θ = 1 2\theta=1 2 θ = 1 . In both cases σ t , n 2 ( z ) ≤ C σ , t 2 n ˉ − 2 θ \sigma_{t,n}^2(\mathbf{z})\le C_{\sigma,t}^2\bar{n}^{-2\theta} σ t , n 2 ( z ) ≤ C σ , t 2 n ˉ − 2 θ .
:::
Lemma 12 (Error propagation). Let Assumption 2(ii) hold and fix n n n . For all t ≤ T − 1 t\le T-1 t ≤ T − 1 and all z ∈ Z \mathbf{z}\in\mathcal{Z} z ∈ Z , with the expectation taken over the next state alone,
e t n ( z ) ≤ ∣ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) ∣ + E x ′ ∼ P t ( ⋅ ∣ z ) [ sup u ∈ U e t + 1 n ( x ′ , u ) ] . (28) e_t^n(\mathbf{z})\le\left|\mu_t^n(\mathbf{z})-(\mathcal{T}_t\mu_{t+1}^n)(\mathbf{z})\right|+\mathbb{E}_{\mathbf{x}'\sim P_t(\cdot\mid\mathbf{z})}\left[\sup_{u\in\mathcal{U}}e_{t+1}^n(\mathbf{x}',u)\right]. \tag*{(28)} e t n ( z ) ≤ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) + E x ′ ∼ P t ( ⋅ ∣ z ) [ u ∈ U sup e t + 1 n ( x ′ , u ) ] . (28) If in addition the closure condition of Assumption 2(iv) holds and sup z ∈ Z t ∣ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) ∣ ≤ ι t \sup_{\mathbf{z}\in\mathcal{Z}_t}|\mu_t^n(\mathbf{z})-(\mathcal{T}_t\mu_{t+1}^n)(\mathbf{z})|\le\iota_t sup z ∈ Z t ∣ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) ∣ ≤ ι t for every t ≤ T − 1 t\le T-1 t ≤ T − 1 , then
sup z ∈ Z t e t n ( z ) ≤ ∑ j = t T − 1 ι j for every t ≤ T − 1. \sup_{\mathbf{z}\in\mathcal{Z}_t}e_t^n(\mathbf{z})\le\sum_{j=t}^{T-1}\iota_j\qquad\text{for every }t\le T-1. z ∈ Z t sup e t n ( z ) ≤ j = t ∑ T − 1 ι j for every t ≤ T − 1.
Lemma 12 gives Theorem 7 (b) and adds the errors of the time steps into the sum of Theorem 7 (c).
Proof. Since e t + 1 n e_{t+1}^{n} e t + 1 n is continuous on the compact Z \mathcal{Z} Z , x ′ ↦ sup u e t + 1 n ( x ′ , u ) \mathbf{x}' \mapsto\sup_{\mathbf{u}} e_{t+1}^{n}(\mathbf{x}',\mathbf{u}) x ′ ↦ sup u e t + 1 n ( x ′ , u ) is continuous and the expectation in (28) is well defined. The error at time step t t t splits into the error of one regression step and the error passed on from time step t + 1 t+1 t + 1 . By (19) and the triangle inequality,
e t n ( z ) ≤ ∣ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) ∣ + ∣ ( T t μ t + 1 n − T t Q t + 1 ∗ ) ( z ) ∣ , e_{t}^{n}(\mathbf{z}) \leq\left|\mu_{t}^{n}(\mathbf{z})-(\mathcal{T}_{t}\mu_{t+1}^{n})(\mathbf{z})\right|+\left|(\mathcal{T}_{t}\mu_{t+1}^{n}-\mathcal{T}_{t}Q_{t+1}^{*})(\mathbf{z})\right|, e t n ( z ) ≤ μ t n ( z ) − ( T t μ t + 1 n ) ( z ) + ( T t μ t + 1 n − T t Q t + 1 ∗ ) ( z ) ,
and by (16) the second term is at most the expectation in (28) . At t = T − 1 t=T-1 t = T − 1 it vanishes, since both greedy values are clipped onto [ 0 , 0 ] [0,0] [ 0 , 0 ] . For the second claim, let Δ t : = sup z ∈ Z t e t n ( z ) \Delta_t:=\sup_{\mathbf{z}\in\mathcal{Z}_t}e_t^n(\mathbf{z}) Δ t := sup z ∈ Z t e t n ( z ) and Δ T : = 0 \Delta_T:=0 Δ T := 0 . For t ≤ T − 2 t\leq T-2 t ≤ T − 2 and z ∈ Z t \mathbf{z}\in\mathcal{Z}_t z ∈ Z t , closure keeps the next state in X t + 1 \mathcal{X}_{t+1} X t + 1 almost surely, so the expectation in (28) is at most Δ t + 1 \Delta_{t+1} Δ t + 1 . Hence Δ t ≤ ι t + Δ t + 1 \Delta_t\leq\iota_t+\Delta_{t+1} Δ t ≤ ι t + Δ t + 1 for every t ≤ T − 1 t\leq T-1 t ≤ T − 1 , and summing gives the claim. ■
Proof [Proof of Theorem 7 ] The proof combines the three steps. Apply Lemma 10 with A n = 1 A_n=1 A n = 1 , the variance assignment of the algorithm and the radii R t , n : = β t , n ( δ ) R_{t,n}:=\beta_{t,n}(\delta) R t , n := β t , n ( δ ) , so that its width is β t , n ( δ ) \beta_{t,n}(\delta) β t , n ( δ ) , and work on the event, of probability at least 1 − 2 δ 1-2\delta 1 − 2 δ , on which it and Lemma 11 hold.
Part (a). Fix n n n . By backward induction, ∥ μ t n ∥ κ ≤ β t , n ( δ ) \lVert\mu_t^n\rVert_{\kappa}\leq\beta_{t,n}(\delta) ∥ μ t n ∥ κ ≤ β t , n ( δ ) for all t t t . This holds at t = T t=T t = T . If it holds at t + 1 t+1 t + 1 , Lemma 10, being uniform over the ball of radius β t + 1 , n ( δ ) \beta_{t+1,n}(\delta) β t + 1 , n ( δ ) , applies to the data-dependent g = μ t + 1 n g=\mu_{t+1}^n g = μ t + 1 n , and by (18) its part (b) is the norm bound at t t t and its part (a) is the claim. Part (b) follows from (a) and (28) . For n ≥ n 0 ( δ ) n\geq n_0(\delta) n ≥ n 0 ( δ ) , part (c) follows from (a), Lemma 11 and Lemma 12 with ι t = C σ , t β t , n ( δ ) n ˉ − θ \iota_t=C_{\sigma,t}\beta_{t,n}(\delta)\bar{n}^{-\theta} ι t = C σ , t β t , n ( δ ) n ˉ − θ .
Almost-sure convergence. Let E \mathcal{E} E be the event that μ t n → Q t ∗ \mu_t^n\to Q_t^* μ t n → Q t ∗ uniformly on Z t \mathcal{Z}_t Z t for every t t t . Under the condition of the theorem, (c) shows that E \mathcal{E} E contains an event of probability at least 1 − 2 δ 1-2\delta 1 − 2 δ for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , so P ( E ) = 1 \mathbb{P}(\mathcal{E})=1 P ( E ) = 1 . ■
Rates
The widths β t , n ( δ ) \beta_{t,n}(\delta) β t , n ( δ ) grow with γ n \gamma_n γ n and N n \mathcal{N}_n N n , and the corollary below turns polynomial bounds on both into a rate. We write f n ( δ ) = O ~ ( g n ) f_n(\delta)=\widetilde{O}(g_n) f n ( δ ) = O ( g n ) if f n ( δ ) ≤ C g n log p ( e n / δ ) f_n(\delta)\leq Cg_n\log^p(en/\delta) f n ( δ ) ≤ C g n log p ( e n / δ ) for constants C C C and p ≥ 0 p\geq0 p ≥ 0 that depend on neither n n n nor δ \delta δ .
Corollary 13 (Rates under polynomial complexity). Let Assumption 2 hold, and suppose that there is an exponent ψ ∈ ( 0 , 1 ) \psi\in(0,1) ψ ∈ ( 0 , 1 ) with the following two properties.
(P1) There are constants C γ C_\gamma C γ and p γ ≥ 0 p_\gamma\geq0 p γ ≥ 0 such that γ n ( λ ) ≤ C γ max { 1 , ( n / λ ) ψ } log p γ ( e + n / λ ) \gamma_n(\lambda)\leq C_\gamma\max\{1,(n/\lambda)^\psi\}\log^{p_\gamma}(e+n/\lambda) γ n ( λ ) ≤ C γ max { 1 , ( n / λ ) ψ } log p γ ( e + n / λ ) for all n ≥ 1 n\geq1 n ≥ 1 and all λ ≥ λ − \lambda\geq\lambda_- λ ≥ λ − .
(P2) There is a constant C N C_{\mathcal{N}} C N such that, for all 0 < τ ≤ R 0<\tau\leq R 0 < τ ≤ R , the ball { g ∈ H κ : ∥ g ∥ κ ≤ R } \{g\in\mathcal{H}_{\kappa}:\lVert g\rVert_{\kappa}\leq R\} { g ∈ H κ : ∥ g ∥ κ ≤ R } is covered by exp ( C N ( R / τ ) 2 ψ ) \exp(C_{\mathcal{N}}(R/\tau)^{2\psi}) exp ( C N ( R / τ ) 2 ψ ) balls of radius τ \tau τ in the supremum norm on Z \mathcal{Z} Z with centres in it.
Let ζ ∈ [ 0 , 1 ) \zeta\in[0,1) ζ ∈ [ 0 , 1 ) , let D n : = max { 1 , n ˉ ψ / χ n } D_n:=\max\{1,\bar{n}^{\psi/\chi_n}\} D n := max { 1 , n ˉ ψ / χ n } and choose the resolution τ n : = D n / n ˉ \tau_n:=\sqrt{D_n/\bar{n}} τ n := D n / n ˉ . Then β t , n ( δ ) = O ~ ( D n ) \beta_{t,n}(\delta)=\widetilde{O}(\sqrt{D_n}) β t , n ( δ ) = O ( D n ) for every t t t . Moreover, there are constants C C C and p ≥ 0 p\geq0 p ≥ 0 such that, for every δ ∈ ( 0 , 1 ) \delta\in(0,1) δ ∈ ( 0 , 1 ) , with probability at least 1 − 2 δ 1-2\delta 1 − 2 δ , for all n ≥ n 0 ( δ ) n\geq n_0(\delta) n ≥ n 0 ( δ ) and all t t t ,
sup z ∈ Z t e t n ( z ) ≤ C n − ξ ( ζ ) log p ( e n / δ ) , ξ ( ζ ) : = ( 1 − ζ ) θ − 1 2 max { 0 , ( 1 − ζ ) ψ − ζ } . \sup_{\mathbf{z}\in\mathcal{Z}_t}e_t^n(\mathbf{z})\leq Cn^{-\xi(\zeta)}\log^p(en/\delta),\qquad\xi(\zeta):=(1-\zeta)\theta-\frac{1}{2}\max\{0,(1-\zeta)\psi-\zeta\}. z ∈ Z t sup e t n ( z ) ≤ C n − ξ ( ζ ) log p ( e n / δ ) , ξ ( ζ ) := ( 1 − ζ ) θ − 2 1 max { 0 , ( 1 − ζ ) ψ − ζ } .
The exponent ξ ( ζ ) \xi(\zeta) ξ ( ζ ) is largest at ζ ∗ : = ψ / ( 1 + ψ ) \zeta^* := \psi/(1+\psi) ζ ∗ := ψ / ( 1 + ψ ) , where D n = 1 D_n=1 D n = 1 and
ξ ( ζ ∗ ) = θ 1 + ψ > 0 , whereas ξ ( 0 ) = θ − ψ 2 . \xi(\zeta^*) = \frac{\theta}{1+\psi} > 0, \qquad\text{whereas} \qquad\xi(0) = \theta- \frac{\psi}{2}. ξ ( ζ ∗ ) = 1 + ψ θ > 0 , whereas ξ ( 0 ) = θ − 2 ψ .
If ξ ( ζ ) > 0 \xi(\zeta)>0 ξ ( ζ ) > 0 , then μ t n → Q t ∗ \mu_t^n \to Q_t^* μ t n → Q t ∗ uniformly on Z t \mathcal{Z}_t Z t almost surely, for every t t t .
Proof. Each of the three terms of the width grows at most as D n \sqrt{D_n} D n , up to logarithmic factors. By backward induction on t t t , β t , n ( δ ) = O ~ ( D n ) \beta_{t,n}(\delta)=\widetilde{O}(\sqrt{D_n}) β t , n ( δ ) = O ( D n ) . The function-norm term of (21) is constant, and the discretisation term equals 2 D n / λ − 2\sqrt{D_n}/\lambda_- 2 D n / λ − by the choice of τ n \tau_n τ n . In the noise term, (P1) gives γ n ( χ n λ − ) = O ~ ( n ˉ ψ ) \gamma_n(\chi_n\lambda_-)=\widetilde{O}(\bar{n}^{\psi}) γ n ( χ n λ − ) = O ( n ˉ ψ ) , and (P2) with R = β t + 1 , n ( δ ) = O ~ ( D n ) R=\beta_{t+1,n}(\delta)=\widetilde{O}(\sqrt{D_n}) R = β t + 1 , n ( δ ) = O ( D n ) gives N n ( R ) = O ~ ( n ˉ ψ ) \mathcal{N}_n(R)=\widetilde{O}(\bar{n}^{\psi}) N n ( R ) = O ( n ˉ ψ ) , or N n ( R ) ≤ C N \mathcal{N}_n(R)\le C_N N n ( R ) ≤ C N if R < τ n R<\tau_n R < τ n . Since n ˉ ψ / χ n ≤ D n \bar{n}^{\psi}/\chi_n\le D_n n ˉ ψ / χ n ≤ D n , the noise term is O ~ ( D n ) \widetilde{O}(\sqrt{D_n}) O ( D n ) . Theorem 7 (c) then bounds the error by O ( D n n ˉ − θ ) = O ~ ( n − ξ ( ζ ) ) O(\sqrt{D_n}\,\bar{n}^{-\theta})=\widetilde{O}(n^{-\xi(\zeta)}) O ( D n n ˉ − θ ) = O ( n − ξ ( ζ ) ) , since n ˉ = n 1 − ζ \bar{n}=n^{1-\zeta} n ˉ = n 1 − ζ and n ˉ ψ / χ n = n ( 1 − ζ ) ψ − ζ \bar{n}^{\psi}/\chi_n=n^{(1-\zeta)\psi-\zeta} n ˉ ψ / χ n = n ( 1 − ζ ) ψ − ζ . Because θ ≤ 1 / 2 \theta\le1/2 θ ≤ 1/2 , the exponent ξ \xi ξ increases in ζ \zeta ζ up to ζ ∗ \zeta^* ζ ∗ , where ( 1 − ζ ∗ ) ψ = ζ ∗ (1-\zeta^*)\psi=\zeta^* ( 1 − ζ ∗ ) ψ = ζ ∗ and D n = 1 D_n=1 D n = 1 , and decreases beyond it. If ξ ( ζ ) > 0 \xi(\zeta)>0 ξ ( ζ ) > 0 , then n ˉ − θ β j , n ( δ ) → 0 \bar{n}^{-\theta}\beta_{j,n}(\delta)\to0 n ˉ − θ β j , n ( δ ) → 0 and the almost-sure statement of Theorem 7 applies.
Matérn kernels. Let κ \kappa κ be a Matérn kernel with smoothness ν > 1 / 2 \nu>1/2 ν > 1/2 and let ψ : = d / ( 2 ν + d ) \psi:=d/(2\nu+d) ψ := d / ( 2 ν + d ) . Property (P2) holds with this ψ \psi ψ , because H κ \mathcal{H}_{\kappa} H κ is norm-equivalent to the Sobolev space of order ν + d / 2 \nu+d/2 ν + d /2 on Z \mathcal{Z} Z ([33 ] ), whose balls have metric entropy of order ( R / τ ) d / ( ν + d / 2 ) (R/\tau)^{d/(\nu+d/2)} ( R / τ ) d / ( ν + d /2 ) in the supremum norm ([17 ] ). Property (P1) holds with the same ψ \psi ψ if the eigenfunctions of the kernel are uniformly bounded ([54 ] ). With L κ > 0 L_{\kappa}>0 L κ > 0 , Corollary 13 gives
ξ ( 0 ) = 4 q ν − d 2 2 ( 2 q + d ) ( 2 ν + d ) and ξ ( ζ ∗ ) = q ( 2 ν + d ) ( 2 q + d ) ( 2 ν + 2 d ) with ζ ∗ = d 2 ν + 2 d . \xi(0)=\frac{4q\nu-d^2}{2(2q+d)(2\nu+d)}
\qquad\text{and}\qquad
\xi(\zeta^*)=\frac{q(2\nu+d)}{(2q+d)(2\nu+2d)}
\qquad\text{with}\qquad
\zeta^*=\frac{d}{2\nu+2d}. ξ ( 0 ) = 2 ( 2 q + d ) ( 2 ν + d ) 4 q ν − d 2 and ξ ( ζ ∗ ) = ( 2 q + d ) ( 2 ν + 2 d ) q ( 2 ν + d ) with ζ ∗ = 2 ν + 2 d d .
Without a schedule the bound tends to zero if d 2 < 4 q ν d^2<4q\nu d 2 < 4 q ν , so for d ≤ 3 d\le3 d ≤ 3 with the Matérn-5/2 kernel (ν = 5 / 2 \nu=5/2 ν = 5/2 , q = 1 q=1 q = 1 ). With the schedule χ n = n d / ( 2 ν + 2 d ) \chi_n=n^{d/(2\nu+2d)} χ n = n d / ( 2 ν + 2 d ) it tends to zero in every dimension and the confidence width stays polylogarithmic. Whitehouse et al. (2023) use the same device, a regulariser that grows as a power of the number of observations, to obtain sublinear regret for GP-UCB with every Matérn kernel.
Implementation details
Terminal value and clipping. For t < T − 1 t<T-1 t < T − 1 the maximum in the target (3) is clipped to the range of returns from time step t + 1 t+1 t + 1 , V t + 1 ( x ) : = Π t + 1 max u ∈ U μ t + 1 ( x , u ) V_{t+1}(\mathbf{x}):=\Pi_{t+1} \max_{\mathbf{u}\in\mathcal{U}}\mu_{t+1}(\mathbf{x},\mathbf{u}) V t + 1 ( x ) := Π t + 1 max u ∈ U μ t + 1 ( x , u ) , where Π t + 1 \Pi_{t+1} Π t + 1 clips to the interval from ( T − t − 1 ) r min + r min T (T-t-1)r_{\min}+r_{\min}^{T} ( T − t − 1 ) r m i n + r m i n T to ( T − t − 1 ) r max + r max T (T-t-1)r_{\max}+r_{\max}^{T} ( T − t − 1 ) r m a x + r m a x T , so that an overestimated maximum does not propagate backwards. The terminal value is
V T ( x i ′ ) : = r ˉ T ( x i ′ ) , V T ( x i ′ ) : = r T , i , or V T ( x i ′ ) : = Π T ( μ T ( x i ′ ) ) , (29) V_T(\mathbf{x}_i'):=\bar{r}_T(\mathbf{x}_i'), \qquad V_T(\mathbf{x}_i'):=r_{T,i}, \qquad\text{or} \qquad V_T(\mathbf{x}_i'):=\Pi_T(\mu_T(\mathbf{x}_i')), \tag*{(29)} V T ( x i ′ ) := r ˉ T ( x i ′ ) , V T ( x i ′ ) := r T , i , or V T ( x i ′ ) := Π T ( μ T ( x i ′ )) , (29)
The first applies when r ˉ T \bar{r}_T r ˉ T is a known function of the state, as in the synthetic MDPs (Appendix § 10 ). The second uses the terminal reward r T , i r_{T,i} r T , i measured in the episode of transition i i i , which is equivalent to adding it to r T − 1 r_{T-1} r T − 1 . The third fits a GP R T ∼ G P ( μ T , Σ T ) R_T\sim\mathcal{GP}(\mu_T,\Sigma_T) R T ∼ G P ( μ T , Σ T ) on the d x d_x d x state coordinates to past measured pairs ( x T , r T ) (\mathbf{x}_T,r_T) ( x T , r T ) , with Π T \Pi_T Π T clipping to [ r min T , r max T ] [r_{\min}^{T},r_{\max}^{T}] [ r m i n T , r m a x T ] , which pools the measurements of nearby final states. Without a terminal reward, V T ≡ 0 V_T\equiv0 V T ≡ 0 , as in the five benchmarks, which give the reward of the final state on the last transition (Appendix C).
Fitting the GPs. After each episode the GP of every time step is refitted. Inputs are scaled to [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] by the state and input bounds, and targets are standardised to zero mean and unit variance. The Matérn-5/2 kernel has a signal variance in [ 0.1 , 10 ] [0.1,10] [ 0.1 , 10 ] and one lengthscale per input dimension in [ 0.5 , 10 ] [0.5,10] [ 0.5 , 10 ] , fitted by marginal likelihood. The variances ω t ( z i ) \omega_t(z_i) ω t ( z i ) start from a single level fitted by marginal likelihood with the kernel and are then estimated as in the most likely heteroscedastic GP of Kersting et al. [34 ] . With the current variances, the leave-one-out residual e i = y t , i − μ t , − i ( z i ) e_i = y_{t,i} - \mu_{t,-i}(z_i) e i = y t , i − μ t , − i ( z i ) and its predictive variance s i 2 s_i^2 s i 2 follow in closed form from one inverse of K + Λ t K + \Lambda_t K + Λ t (Rasmussen and Williams [46 ] ). A second GP, of the same kernel family with its own hyperparameters and Gaussian noise level fitted by marginal likelihood, regresses log e i 2 \log e_i^2 log e i 2 on the inputs. With m ( z ) m(z) m ( z ) its posterior mean, the update is ω t ( z i ) ← exp ( m ( z i ) + 1.27 ) − ( s i 2 − ω t ( z i ) ) \omega_t(z_i) \leftarrow\exp(m(z_i) + 1.27) - (s_i^2 - \omega_t(z_i)) ω t ( z i ) ← exp ( m ( z i ) + 1.27 ) − ( s i 2 − ω t ( z i )) , clipped to [ 10 − 6 , 1 ] [10^{-6},1] [ 1 0 − 6 , 1 ] in standardised units. Here exp ( m + 1.27 ) \exp(m + 1.27) exp ( m + 1.27 ) estimates the expected squared residual, with 1.27 = − E [ log χ 1 2 ] 1.27 = -\mathbb{E}[\log\chi_1^2] 1.27 = − E [ log χ 1 2 ] the bias of the logarithm, so m t m_t m t of § 3.3 is m + 1.27 m + 1.27 m + 1.27 , and s i 2 − ω t ( z i ) s_i^2 - \omega_t(z_i) s i 2 − ω t ( z i ) is the GP’s leave-one-out predictive variance plus the floor σ r 2 \sigma_r^2 σ r 2 . The kernel is then refitted with these variances fixed, and the two steps alternate twice. For the sparse GP of Appendix § 12 , the leave-one-out quantities follow by the Woodbury identity at cost O ( n m 2 ) O(nm^2) O ( n m 2 ) , and the GP on the log residuals is sparse as well. On the LMDP the kernel is linear in the features of Appendix § 11 and fixed.
Behaviour policy and maximisation. Each of the N 0 N_0 N 0 initial episodes (§ 5.1 ) applies the inputs of its own scrambled Sobol sequence over U \mathcal{U} U . Thompson samples Q ~ t \widetilde{Q}_t Q t are drawn as whole functions by pathwise conditioning (Wilson et al. (2020)), a random-Fourier-feature prior sample (Rahimi and Recht [45 ] ) corrected by Matheron’s rule, so they are smooth with analytic gradients. Every maximisation over inputs (of Q ~ t \widetilde{Q}_t Q t when acting, of μ t + 1 \mu_{t+1} μ t + 1 for the targets and of μ t \mu_t μ t for the greedy policy) evaluates the function on a fixed candidate set, runs L-BFGS-B (Byrd et al. [12 ] ) over U \mathcal{U} U from the best candidates, and returns the best input found (settings in Appendix § 11 ).
Computational cost. After n n n episodes a backward pass solves T T T linear systems of size N 0 + n N_0+n N 0 + n , at cost O ( T ( N 0 + n ) 3 ) O(T(N_0+n)^3) O ( T ( N 0 + n ) 3 ) , plus the maximisations for the targets. For our budgets (n ≤ 300 n \le300 n ≤ 300 ) this is small compared with a physical experiment. Appendix § 12 measures the cost of the exact fit and of a sparse fit (Titsias [51 ] ) for larger budgets.
Benchmark models
Table 2 summarises the five benchmarks.
Table 2. Benchmarks: state dimension d x d_x d x , input dimension d u d_u d u , horizon T T T and reward.
Non-stationary linear MDP
The state x t = [ p t , v t ] ⊤ \mathbf{x}_t = [p_t, v_t]^{\top} x t = [ p t , v t ] ⊤ evolves as
x t + 1 = A x t + B u t + w t , A = [ 1 Δ t 0 1 ] , B = [ 1 2 Δ t 2 Δ t ] , (30) \mathbf{x}_{t+1} = A\mathbf{x}_t + B\mathbf{u}_t + \mathbf{w}_t,\qquad A = \begin{bmatrix} 1 & \Delta t \\ 0 & 1 \end{bmatrix},\qquad B = \begin{bmatrix} \frac{1}{2}\Delta t^2 \\ \Delta t \end{bmatrix}, \tag*{(30)} x t + 1 = A x t + B u t + w t , A = [ 1 0 Δ t 1 ] , B = [ 2 1 Δ t 2 Δ t ] , (30)
with input u t ∈ [ − 1 , 1 ] \mathbf{u}_t \in[-1,1] u t ∈ [ − 1 , 1 ] , time step Δ t = 1.2 \Delta t = 1.2 Δ t = 1.2 and disturbance w t ∼ N ( 0 , σ w 2 I ) \mathbf{w}_t \sim\mathcal{N}(0,\sigma_w^2 I) w t ∼ N ( 0 , σ w 2 I ) , σ w = 0.1 \sigma_w = 0.1 σ w = 0.1 . The horizon is T = 10 T = 10 T = 10 . The reward is linear in the state and the input, with a random coefficient β t \beta_t β t on the input,
r t = − ( A r x t + B r β t u t ) , A r = [ 0.02 , 0 ] , B r = 1 , (31) r_t = -(A_r\mathbf{x}_t + B_r\beta_t\mathbf{u}_t),\qquad A_r = [0.02,0],\qquad B_r = 1, \tag*{(31)} r t = − ( A r x t + B r β t u t ) , A r = [ 0.02 , 0 ] , B r = 1 , (31)
and the coefficient changes sign every two time steps,
β t ∼ { N ( + 1 , σ β 2 ) if ⌊ t / 2 ⌋ m o d 2 = 0 , N ( − 1 , σ β 2 ) otherwise , σ β = 1 , (32) \beta_t \sim\begin{cases} \mathcal{N}(+1,\sigma_\beta^2) & \text{if } \lfloor t/2 \rfloor\bmod2 = 0, \\ \mathcal{N}(-1,\sigma_\beta^2) & \text{otherwise}, \end{cases}\qquad\sigma_\beta= 1, \tag*{(32)} β t ∼ { N ( + 1 , σ β 2 ) N ( − 1 , σ β 2 ) if ⌊ t /2 ⌋ mod 2 = 0 , otherwise , σ β = 1 , (32)
so the controller must anticipate the reversals. Rewards are divided by 100 before learning. Initial states are drawn as p 0 ∼ U ( 3 , 7 ) p_0 \sim\mathcal{U}(3,7) p 0 ∼ U ( 3 , 7 ) and v 0 ∼ U ( − 2 , 2 ) v_0 \sim\mathcal{U}(-2,2) v 0 ∼ U ( − 2 , 2 ) .
Semi-batch reactor
A semi-batch reactor carries out two consecutive reactions,
2 A → k 1 B , (33) 2A \xrightarrow{k_1} B, \tag*{(33)} 2 A k 1 B , (33)
B → k 2 3 C . (34) B \xrightarrow{k_2} 3C. \tag*{(34)} B k 2 3 C . (34)
The state x = [ C A , C B , C C , T r , V ] ⊤ \mathbf{x} = [C_A,C_B,C_C,T_r,V]^{\top} x = [ C A , C B , C C , T r , V ] ⊤ tracks the species concentrations, the reactor temperature T r T_r T r and the liquid volume V V V . The mass balances are
C ˙ A = − k 1 C A + F V ( C A 0 − C A ) , (35) \dot{C}_A = -k_1 C_A + \frac{F}{V}(C_{A0} - C_A), \tag*{(35)} C ˙ A = − k 1 C A + V F ( C A 0 − C A ) , (35)
C ˙ B = 1 2 k 1 C A − k 2 C B − F V C B , (36) \dot{C}_B = \frac{1}{2}k_1 C_A - k_2 C_B - \frac{F}{V}C_B, \tag*{(36)} C ˙ B = 2 1 k 1 C A − k 2 C B − V F C B , (36)
C ˙ C = 3 k 2 C B − F V C C , (37) \dot{C}_C = 3k_2 C_B - \frac{F}{V}C_C, \tag*{(37)} C ˙ C = 3 k 2 C B − V F C C , (37)
V ˙ = F , (38) \dot{V} = F, \tag*{(38)} V ˙ = F , (38)
where F F F is the feed rate. The rate constants follow the Arrhenius relation
k i ( T r ) = A i exp [ E i , A R ( 1 T r , i − 1 T r ) ] , (39) k_i(T_r) = A_i \exp\left[\frac{E_{i,A}}{R}\left(\frac{1}{T_{r,i}}-\frac{1}{T_r}\right)\right], \tag*{(39)} k i ( T r ) = A i exp [ R E i , A ( T r , i 1 − T r 1 ) ] , (39)
and the energy balance is
T ˙ r = U A ( T a − T r ) − F C p , A ( T r − T 0 ) + V ∑ j ( − Δ H r , j ) R j V ∑ i C i C p , i + N H 2 S O 4 C p , H 2 S O 4 . (40) \dot{T}_r = \frac{UA(T_a-T_r)-FC_{p,A}(T_r-T_0)+V\sum_j(-\Delta H_{r,j})R_j}{V\sum_i C_iC_{p,i}+N_{H_2SO_4}C_{p,H_2SO_4}}. \tag*{(40)} T ˙ r = V ∑ i C i C p , i + N H 2 S O 4 C p , H 2 S O 4 U A ( T a − T r ) − F C p , A ( T r − T 0 ) + V ∑ j ( − Δ H r , j ) R j . (40)
where R j \mathcal{R}_j R j is the rate of reaction j j j . The inputs are the feed rate F ∈ [ 0 , 270 ] F \in[0,270] F ∈ [ 0 , 270 ] and the jacket temperature T a ∈ [ 298 , 500 ] T_a \in[298,500] T a ∈ [ 298 , 500 ] . The objective is the amount of product C C C at the end of the batch, given as a reward on the final transition only,
r t = { C C , T V T ( C C V ) max , t = T − 1 , 0 , otherwise , (41) r_t =
\begin{cases}
\frac{C_{C,T}V_T}{(C_CV)_{\max}}, & t=T-1,\\
0, & \text{otherwise},
\end{cases} \tag*{(41)} r t = { ( C C V ) m a x C C , T V T , 0 , t = T − 1 , otherwise , (41)
where C C , T C_{C,T} C C , T and V T V_T V T are reached after applying u T − 1 \mathbf{u}_{T-1} u T − 1 , and ( C C V ) max (C_CV)_{\max} ( C C V ) m a x , the largest attainable amount of product, maps the best achievable reward to one. The temperature and volume are constrained to T r ≤ 420 K T_r \le420\,\mathrm{K} T r ≤ 420 K and V ≤ 800 L V \le800\,\mathrm{L} V ≤ 800 L . Every time step subtracts the penalty 0.5 ∑ k max ( 0 , g k / g ˉ k − 1 ) 0.5\sum_k \max(0,g_k/\bar{g}_k-1) 0.5 ∑ k max ( 0 , g k / g ˉ k − 1 ) from the reward, where g k g_k g k is a constrained state after the step and g ˉ k \bar{g}_k g ˉ k its bound. Without the penalty the best policy heats the reactor to about 560 K 560\,\mathrm{K} 560 K , and with it the best policy keeps the temperature near its bound.
Stochasticity. Each integration step adds multiplicative Gaussian state noise, x t + 1 ← x t + 1 + ξ t ⊙ x t + 1 \mathbf{x}_{t+1} \leftarrow\mathbf{x}_{t+1}+\boldsymbol{\xi}_t\odot\mathbf{x}_{t+1} x t + 1 ← x t + 1 + ξ t ⊙ x t + 1 with ξ t ∼ N ( 0 , σ x 2 I ) \boldsymbol{\xi}_t \sim\mathcal{N}(0,\sigma_x^2\mathbf{I}) ξ t ∼ N ( 0 , σ x 2 I ) and σ x = 0.02 \sigma_x=0.02 σ x = 0.02 (2% relative noise). Initial states are x 0 = x ˉ 0 + ζ \mathbf{x}_0=\bar{\mathbf{x}}_0+\boldsymbol{\zeta} x 0 = x ˉ 0 + ζ with x ˉ 0 = [ 1.0 , 0.0 , 0.0 , 290.0 , 100.0 ] ⊤ \bar{\mathbf{x}}_0=[1.0,0.0,0.0,290.0,100.0]^\top x ˉ 0 = [ 1.0 , 0.0 , 0.0 , 290.0 , 100.0 ] ⊤ and ζ ∼ U ( [ − 0.2 , 0.2 ] × { 0 } × { 0 } × [ − 10 , 10 ] × [ − 20 , 20 ] ) \boldsymbol{\zeta}\sim\mathcal{U}([-0.2,0.2]\times\{0\}\times\{0\}\times[-10,10]\times[-20,20]) ζ ∼ U ([ − 0.2 , 0.2 ] × { 0 } × { 0 } × [ − 10 , 10 ] × [ − 20 , 20 ]) , with the initial temperature floored at 280 K 280\,\mathrm{K} 280 K and the initial volume at 50 L 50\,\mathrm{L} 50 L . Before each time step the pre-exponential factors A 1 A_1 A 1 and A 2 A_2 A 2 are multiplied by independent factors exp ( s ε − s 2 / 2 ) \exp(s\varepsilon-s^2/2) exp ( s ε − s 2 /2 ) with ε ∼ N ( 0 , 1 ) \varepsilon\sim\mathcal{N}(0,1) ε ∼ N ( 0 , 1 ) and s = 0.6 s=0.6 s = 0.6 , as when catalyst activity, mixing and mass transfer vary between control intervals. The factors have mean one. Through the Arrhenius rates the resulting noise is small while the batch is cold and large near the temperature bound.
Photosynthetic biomass production
This benchmark models light- and nutrient-driven growth of the cyanobacterium Arthrospira platensis and its production of the pigment phycocyanin [8 ] . The state x = [ c x , c N , c q ] ⊤ \mathbf{x}=[c_x,c_N,c_q]^\top x = [ c x , c N , c q ] ⊤ tracks the biomass concentration (g/L), the nitrate concentration (mg/L) and the phycocyanin concentration (g/L), with
c ˙ x = g ( I , c N ) c x − u d c x , (42) \dot{c}_x=g(I,c_N)c_x-u_dc_x, \tag*{(42)} c ˙ x = g ( I , c N ) c x − u d c x , (42)
c ˙ N = − Y N X g ( I , c N ) c x + F N , (43) \dot{c}_N=-Y_{NX}g(I,c_N)c_x+F_N, \tag*{(43)} c ˙ N = − Y N X g ( I , c N ) c x + F N , (43)
c ˙ q = k m I I + k s q + I 2 / k i q c x − k d c q c N + K N q , (44) \dot{c}_q=\frac{k_{m}I}{I+k_{sq}+I^2/k_{iq}}c_x-\frac{k_dc_q}{c_N+K_{Nq}}, \tag*{(44)} c ˙ q = I + k s q + I 2 / k i q k m I c x − c N + K N q k d c q , (44)
where the light- and nitrate-limited specific growth rate is
g ( I , c N ) = u m I I + k s + I 2 / k i ⋅ c N c N + k N , (45) g(I,c_N)=\frac{u_mI}{I+k_s+I^2/k_i}\cdot\frac{c_N}{c_N+k_N}, \tag*{(45)} g ( I , c N ) = I + k s + I 2 / k i u m I ⋅ c N + k N c N , (45)
and the light intensity I I I and the nitrate feed rate F N F_N F N are the inputs. The kinetic parameters are u m = 0.0572 u_m=0.0572 u m = 0.0572 , u d = 0 u_d=0 u d = 0 , Y N X = 504.5 Y_{NX}=504.5 Y N X = 504.5 , k m = 1.6 × 10 − 4 k_m=1.6\times10^{-4} k m = 1.6 × 1 0 − 4 , k d = 0.281 k_d=0.281 k d = 0.281 , k s q = 23.51 k_{sq}=23.51 k s q = 23.51 , K N q = 16.89 K_{Nq}=16.89 K N q = 16.89 , k i q = 800 k_{iq}=800 k i q = 800 , k s = 178.9 k_s=178.9 k s = 178.9 , k i = 447.1 k_i=447.1 k i = 447.1 and k N = 393.1 k_N=393.1 k N = 393.1 . The inputs are constrained to I ∈ [ 120 , 400 ] μ E / m 2 / s I\in[120,400]\,\mu\mathrm{E}/\mathrm{m}^2/\mathrm{s} I ∈ [ 120 , 400 ] μ E / m 2 / s and F N ∈ [ 0 , 40 ] m g / L / h F_N\in[0,40]\,\mathrm{mg}/\mathrm{L}/\mathrm{h} F N ∈ [ 0 , 40 ] mg / L / h , and the states are scaled for the GP by the ranges c x ∈ [ 0 , 20 ] g / L c_x\in[0,20]\,\mathrm{g}/\mathrm{L} c x ∈ [ 0 , 20 ] g / L , c N ∈ [ 0 , 7000 ] m g / L c_N\in[0,7000]\,\mathrm{mg}/\mathrm{L} c N ∈ [ 0 , 7000 ] mg / L and c q ∈ [ 0 , 0.15 ] g / L c_q\in[0,0.15]\,\mathrm{g}/\mathrm{L} c q ∈ [ 0 , 0.15 ] g / L . The objective is the final biomass, given as a reward on the final transition only,
r t = { c x , T c x , max , t = T − 1 , 0 , otherwise , (46) r_t =
\begin{cases}
\frac{c_{x,T}}{c_{x,\max}}, & t = T-1,\\
0, & \text{otherwise},
\end{cases} \tag*{(46)} r t = { c x , m a x c x , T , 0 , t = T − 1 , otherwise , (46)
where c x , T c_{x,T} c x , T is reached after applying u T − 1 \mathbf{u}_{T-1} u T − 1 , and c x , max ≈ 17.0 c_{x,\max} \approx17.0 c x , m a x ≈ 17.0 g/L is the largest final biomass reached by constant inputs within the bounds (found by a grid search), which maps that value to one. The nitrate concentration is constrained to c N ≤ 800 c_N \le800 c N ≤ 800 mg/L, which a penalty enforces: every time step subtracts the penalty 0.05 max ( 0 , c N / 800 − 1 ) 0.05\max(0,c_N/800-1) 0.05 max ( 0 , c N /800 − 1 ) from the reward. Rewards are divided by 10 before learning.
Stochasticity. Each integration step adds multiplicative Gaussian state noise as above with σ x = 0.001 \sigma_x = 0.001 σ x = 0.001 (0.1% relative noise). Initial states are x 0 = x ˉ 0 + ζ \mathbf{x}_0 = \bar{\mathbf{x}}_0 + \boldsymbol{\zeta} x 0 = x ˉ 0 + ζ with x ˉ 0 = [ 0.1 , 20.0 , 0.01 ] T \bar{\mathbf{x}}_0 = [0.1, 20.0, 0.01]^{\mathsf{T}} x ˉ 0 = [ 0.1 , 20.0 , 0.01 ] T and ζ ∼ U ( [ − 0.02 , 0.02 ] × [ − 2.0 , 2.0 ] × [ − 0.002 , 0.002 ] ) \boldsymbol{\zeta} \sim U([-0.02, 0.02] \times[-2.0, 2.0] \times[-0.002, 0.002]) ζ ∼ U ([ − 0.02 , 0.02 ] × [ − 2.0 , 2.0 ] × [ − 0.002 , 0.002 ]) , floored at zero componentwise. Before each time step the maximum specific growth rate u m u_m u m is multiplied by a factor exp ( s ε − s 2 / 2 ) \exp(s\varepsilon- s^2/2) exp ( s ε − s 2 /2 ) with ε ∼ N ( 0 , 1 ) \varepsilon\sim\mathcal{N}(0,1) ε ∼ N ( 0 , 1 ) and s = 0.6 s = 0.6 s = 0.6 , as when culture temperature and light vary between control intervals. The resulting noise grows with the biomass density and the growth rate, so it is small early in the batch and large near its end. The horizon is T = 8 T = 8 T = 8 time steps over a simulated window of 240 hours.
Inverted pendulum
A pendulum of mass m = 1 m = 1 m = 1 and length l = 1 l = 1 l = 1 under gravity g = 9.8 g = 9.8 g = 9.8 has angle θ \theta θ , zero when upright, and angular velocity θ ˙ \dot{\theta} θ ˙ . The input is a torque u ∈ [ − 2 , 2 ] u \in[-2, 2] u ∈ [ − 2 , 2 ] , and
θ ¨ = 3 g 2 l sin θ + 3 m l 2 u , (47) \ddot{\theta} = \frac{3g}{2l}\sin\theta+ \frac{3}{ml^2}u, \tag*{(47)} θ ¨ = 2 l 3 g sin θ + m l 2 3 u , (47)
integrated by the explicit Euler method with two substeps per time step of Δ t = 0.2 \Delta t = 0.2 Δ t = 0.2 , over T = 20 T = 20 T = 20 time steps. The controller observes [ sin θ , cos θ , θ ˙ ] T [\sin\theta, \cos\theta, \dot{\theta}]^{\mathsf{T}} [ sin θ , cos θ , θ ˙ ] T , which avoids the discontinuity of the angle at ± π \pm\pi ± π , and θ ˙ \dot{\theta} θ ˙ is scaled by the bound 8 for the GP inputs. The pendulum starts hanging down and must be swung up. Each time step costs 0.05 u t 2 Δ t 0.05u_t^2\Delta t 0.05 u t 2 Δ t , and the final time step is instead rewarded by
r T − 1 = − ∣ θ T ∣ − 0.1 ∣ θ ˙ T ∣ , (48) r_{T-1} = -|\theta_T| - 0.1|\dot{\theta}_T|, \tag*{(48)} r T − 1 = − ∣ θ T ∣ − 0.1∣ θ ˙ T ∣ , (48)
with θ \theta θ not wrapped. Rewards are divided by 10 before learning.
Stochasticity. Initial states are θ 0 ∼ N ( π , 0.3 2 ) \theta_0 \sim\mathcal{N}(\pi,0.3^2) θ 0 ∼ N ( π , 0. 3 2 ) and θ ˙ 0 ∼ N ( 0 , 0.3 2 ) \dot{\theta}_0 \sim\mathcal{N}(0,0.3^2) θ ˙ 0 ∼ N ( 0 , 0. 3 2 ) . After each time step, N ( 0 , 0.05 2 ) \mathcal{N}(0,0.05^2) N ( 0 , 0.0 5 2 ) is added to θ ˙ \dot{\theta} θ ˙ , a random external torque.
Target tracking
A point mass with position p = ( y , z ) \mathbf{p} = (y,z) p = ( y , z ) and unit mass hangs in unit gravity from a spring of unit stiffness attached to an anchor a = ( a y , a z ) \mathbf{a} = (a_y,a_z) a = ( a y , a z ) , whose rate of change is the input u = a ˙ ∈ [ − 1 , 1 ] 2 \mathbf{u} = \dot{\mathbf{a}} \in[-1,1]^2 u = a ˙ ∈ [ − 1 , 1 ] 2 . The state x = [ a , p , p ˙ ] T ∈ R 6 \mathbf{x} = [\mathbf{a},\mathbf{p},\dot{\mathbf{p}}]^{\mathsf{T}} \in\mathbb{R}^{6} x = [ a , p , p ˙ ] T ∈ R 6 evolves as
a ˙ = u , p ¨ = − ( p − a ) − [ 0 1 ] , (49) \dot{\mathbf{a}} = \mathbf{u}, \qquad\ddot{\mathbf{p}} = -(\mathbf{p}-\mathbf{a}) -
\begin{bmatrix}
0\\
1
\end{bmatrix}, \tag*{(49)} a ˙ = u , p ¨ = − ( p − a ) − [ 0 1 ] , (49)
integrated by the fourth-order Runge–Kutta method with ten substeps per time step of Δ t = 1 \Delta t = 1 Δ t = 1 , over T = 10 T = 10 T = 10 time steps. Each time step costs 10 − 3 ∥ u t ∥ 2 Δ t 10^{-3}\lVert\mathbf{u}_t\rVert^2\Delta t 1 0 − 3 ∥ u t ∥ 2 Δ t , and the final time step is instead rewarded by
r T − 1 = − ∥ a T ∥ 2 − ∥ p T − p ∗ ∥ 2 , p ∗ = ( 2 , 2 ) , (50) r_{T-1} = -\lVert\mathbf{a}_T\rVert^2 - \lVert\mathbf{p}_T - \mathbf{p}^{*}\rVert^2,\qquad\mathbf{p}^{*} = (2,2), \tag*{(50)} r T − 1 = − ∥ a T ∥ 2 − ∥ p T − p ∗ ∥ 2 , p ∗ = ( 2 , 2 ) , (50)
so the mass must reach the target with the anchor back at the origin. The GP inputs are scaled by the bounds ± 5 \pm5 ± 5 on every state component. Rewards are divided by 10 before learning.
Stochasticity. Initial states are x 0 ∼ N ( 0 , diag ( 0.2 , 0.2 , 0.3 , 0.3 , 0.1 , 0.1 ) 2 ) \mathbf{x}_0 \sim\mathcal{N}(0,\operatorname{diag}(0.2,0.2,0.3,0.3,0.1,0.1)^2) x 0 ∼ N ( 0 , diag ( 0.2 , 0.2 , 0.3 , 0.3 , 0.1 , 0.1 ) 2 ) . After each time step, N ( 0 , 0.03 2 ) \mathcal{N}(0,0.03^2) N ( 0 , 0.0 3 2 ) is added to every state component.
Synthetic MDPs
Both synthetic MDPs of § 5.2 have a state x ∈ [ − 1 , 1 ] x \in[-1,1] x ∈ [ − 1 , 1 ] , an input u ∈ [ − 1 , 1 ] u \in[-1,1] u ∈ [ − 1 , 1 ] , horizon T = 3 T = 3 T = 3 , transitions x ′ = clip ( x + 0.35 u + b ( x ) e , − 1 , 1 ) x' = \operatorname{clip}(x + 0.35u + b(x)e,-1,1) x ′ = clip ( x + 0.35 u + b ( x ) e , − 1 , 1 ) with e ∼ N ( 0 , 1 ) e \sim\mathcal{N}(0,1) e ∼ N ( 0 , 1 ) , a stage reward − 0.05 u 2 -0.05u^2 − 0.05 u 2 and a terminal reward r T ( x ) r_T(x) r T ( x ) . In A, b ( x ) = 0.02 + 0.25 logistic ( − ( x + 0.2 ) / 0.1 ) b(x) = 0.02 + 0.25\operatorname{logistic}(-(x + 0.2)/0.1) b ( x ) = 0.02 + 0.25 logistic ( − ( x + 0.2 ) /0.1 ) and r T ( x ) = 1 − x 2 r_T(x) = 1 - x^2 r T ( x ) = 1 − x 2 . In B, b ( x ) = 0.01 b(x) = 0.01 b ( x ) = 0.01 and r T ( x ) = logistic ( ( x − 0.3 ) / 0.03 ) r_T(x) = \operatorname{logistic}((x - 0.3)/0.03) r T ( x ) = logistic (( x − 0.3 ) /0.03 ) . Each dataset holds 150 transitions per time step with states and inputs drawn uniformly. Every method fits HGPQ’s GP of Appendix § 8 backwards from the terminal reward, with V t + 1 ( x ′ ) V_{t+1}(x') V t + 1 ( x ′ ) the maximum of μ t + 1 ( x ′ , ⋅ ) \mu_{t+1}(x',\cdot) μ t + 1 ( x ′ , ⋅ ) over 51 inputs, and differs only in the target variances: the floor σ r 2 = 10 − 4 \sigma_r^2 = 10^{-4} σ r 2 = 1 0 − 4 , one noise level per time step fitted by marginal likelihood, or HGPQ’s σ r 2 + ω t \sigma_r^2 + \omega_t σ r 2 + ω t . The optimal values come from dynamic programming on a grid of 201 states and 51 inputs. The return gap is the difference between the optimal mean return and that of the greedy policy, simulated from 41 start states with twenty noise draws each.
Results. Table 3 gives the return gap and the mean absolute error of the value learned at time step 1 on a grid of states, averaged over the twenty datasets, for x ≥ 0 x \ge0 x ≥ 0 and for x < 0 x < 0 x < 0 , which in B contains the step of V 1 ∗ V_1^* V 1 ∗ . HGPQ’s gap is smaller than that of one noise level by 0.003 ± 0.003 0.003 \pm0.003 0.003 ± 0.003 in A and 0.012 ± 0.010 0.012 \pm0.010 0.012 ± 0.010 in B (paired over the twenty datasets, 95% intervals), and smaller on fifteen of the twenty datasets in each.
Baselines, protocol and hyperparameters
Baselines. GPQ-CLR (Bloor et al., [7 ] ) and GPQ-SLR, as published, fit one GP over the state, the input and the time step, with one GP per time step only on the LMPD, and use Thompson sampling without the uniform component. They store a value for each visited state–input pair and move it towards its target with a constant or a 1 / N D 1/N_D 1/ N D learning rate. KOVI (Yang et al., 2020) fits a kernel ridge regression at each time step, backwards in time, with a single noise level, and acts on, and bootstraps from, the posterior mean plus a multiple c c c of the posterior standard deviation. GPTD, in its SARSA form ([19 ] ), keeps one GP over the Q-function, observes each reward through the difference of the values of successive state–input pairs, acts on the posterior mean and explores with an annealed ϵ \epsilon ϵ -greedy rule. KTD ([22 ] ) is a Kalman filter on random Fourier features. The deep RL baselines are DQN ([41 ] ), Ensemble-DQN ([42 ] ), DDPG ([37 ] ), TD3 ([21 ] ) and SAC ([26 ] ).
Hyperparameters. HGPQ has no learning rate. Its tuned parameters are the reward noise σ r \sigma_r σ r and, for the constant choice of the target variance, the scale s s s in the constant variance σ r 2 + s κ max \sigma_r^2 + s\ \kappa_{\max} σ r 2 + s κ m a x . Below are the fixed settings of every method, the tuning grids and the selected values (Table 6 ). Every method is tuned on ten seeds (100 to 109) that are not used for evaluation, by the mean final return, with ties within one standard error broken by the area under the learning curve. When the selected value lies at an edge of its grid, the grid is extended beyond that edge by two values at the ratio of the grid and the selection is repeated.
Table 6. Reward bounds of HGPQ and the selected value of every tuned parameter (rewards in the scaled units of Appendix C). DDPG’s critic learning rate is ten times its actor learning rate.
HGPQ. The GPs are fitted as in Appendix § 8 , with the fixed settings of Table 4 . On the LMDP the GP input also contains the features ∣ p t ∣ \lvert p_t\rvert ∣ p t ∣ and sign ( p t ) u t \operatorname{sign}(p_t)\ \mathbf{u}_t sign ( p t ) u t . In the constant variance σ r 2 + s κ max \sigma_r^2 + s\ \kappa_{\max} σ r 2 + s κ m a x ,
Table 4. Fixed settings of HGPQ.
κ max = sup z κ ( z , z ) = σ f 2 \kappa_{\max} = \sup_z \kappa(\mathbf{z}, \mathbf{z}) = \sigma_f^2 κ m a x = z sup κ ( z , z ) = σ f 2
is the prior variance of the kernel refitted at time step t + 1 t+1 t + 1 , in the units of the targets. Table 6 gives the per-step reward bounds [ r min , r max ] [r_{\min}, r_{\max}] [ r m i n , r m a x ] that clip the targets, in the scaled units of Appendix C. We tune σ r ∈ { 10 − 4 , 10 − 3 , 10 − 2 , 0.1 } \sigma_r \in\{10^{-4}, 10^{-3}, 10^{-2}, 0.1\} σ r ∈ { 1 0 − 4 , 1 0 − 3 , 1 0 − 2 , 0.1 } and, for the constant target variance, s ∈ { 0 , 10 − 4 , 5 × 10 − 4 , 2 × 10 − 3 , 10 − 2 , 0.1 , 1 } s \in\{0, 10^{-4}, 5 \times10^{-4}, 2 \times10^{-3}, 10^{-2}, 0.1, 1\} s ∈ { 0 , 1 0 − 4 , 5 × 1 0 − 4 , 2 × 1 0 − 3 , 1 0 − 2 , 0.1 , 1 } jointly. Appendix § 13 reports the sensitivity to σ r \sigma_r σ r and to ϵ \epsilon ϵ .
GPQ-SLR and GPQ-CLR. A GP with HGPQ’s Matérn-5/2 kernel, refit by marginal likelihood, on a table of stored values. Each Bellman target moves its stored value with learning rate 1 / N D 1/N_D 1/ N D (GPQ-SLR, with N D N_D N D the number of stored values) or a constant α \alpha α (GPQ-CLR). Both use HGPQ’s initial episodes and candidate inputs, and Thompson sampling without the uniform component. GPQ-SLR has no free parameter. For GPQ-CLR we tune α ∈ { 0.01 , 0.03 , 0.1 , 0.3 } \alpha\in\{0.01, 0.03, 0.1, 0.3\} α ∈ { 0.01 , 0.03 , 0.1 , 0.3 } , capped at 1.
KOVI. We implement KOVI as in the kernel setting of Yang et al. (2020), with one kernel ridge regression per time step, using a squared-exponential kernel of unit variance on inputs scaled to [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] , refitted by backward induction after every episode, and a bonus proportional to the posterior standard deviation. Every ten episodes, the lengthscale of each time step is chosen by marginal likelihood. KOVI acts on, and bootstraps from, the posterior mean plus c c c posterior standard deviations, clipped to the range of possible returns. Its regulariser λ \lambda λ is the one selected, over { 0.01 , 0.1 , 1 , 10 } \{0.01, 0.1, 1, 10\} { 0.01 , 0.1 , 1 , 10 } , for the same regression without the bonus, with a fixed unit lengthscale and annealed ϵ \epsilon ϵ -greedy exploration, and we tune c ∈ { 0.01 , 0.03 , 0.1 , 0.3 , 1 } c \in\{0.01, 0.03, 0.1, 0.3, 1\} c ∈ { 0.01 , 0.03 , 0.1 , 0.3 , 1 } . Bootstrapped values maximise over 100 candidate inputs, and the behaviour policy over 500, refined by L-BFGS-B.
GPTD. We implement GPTD in its SARSA form (GPSARSA) as Engel et al. [19 ] describe it. A GP models the Q-function, and along each episode every reward is observed through r t = Q t ( z t ) − Q t + 1 ( z t + 1 ) + N t r_t = Q_t(z_t) - Q_{t+1}(z_{t+1}) + N_t r t = Q t ( z t ) − Q t + 1 ( z t + 1 ) + N t , with Q T ≔ 0 Q_T \coloneqq0 Q T : = 0 and the noise of their model for stochastic transitions, whose covariance over an episode is σ 2 H H ⊤ \sigma^2 H H^\top σ 2 H H ⊤ for the temporal-difference matrix H H H . The observation is linear in Q Q Q , so the posterior is exact under this model. For a complete episode H H H is invertible, and the posterior mean is GP regression of the returns-to-go on the visited pairs with noise variance σ 2 \sigma^2 σ 2 , which we compute exactly after every episode. Each time step has an independent GP prior on inputs scaled to [ − 1 , 1 ] [-1, 1] [ − 1 , 1 ] . GPTD acts on the posterior mean, maximised as for KOVI, and explores by ϵ \epsilon ϵ -greedy with ϵ = 10 / ( 10 + k ) \epsilon= 10/(10 + k) ϵ = 10/ ( 10 + k ) in episode k k k . We tune σ 2 ∈ { 10 − 3 , 10 − 2 , 0.1 , 1 } \sigma^2 \in\{10^{-3}, 10^{-2}, 0.1, 1\} σ 2 ∈ { 1 0 − 3 , 1 0 − 2 , 0.1 , 1 } , extended to 10 and 100, or to 10 − 4 10^{-4} 1 0 − 4 and 10 − 5 10^{-5} 1 0 − 5 , where the selected value lay at an edge.
KTD. A linear Kalman filter at each time step on 500 random Fourier features, with prior covariance 10 I 10I 10 I , observation variance 0.1 and process noise 10 − 3 I 10^{-3}I 1 0 − 3 I . We tune the lengthscale of the features over { 0.5 , 1 , 2 } \{0.5, 1, 2\} { 0.5 , 1 , 2 } , extended at an edge as above.
KFQL. Kalman filter Q-learning (Tripp and Shachter [52 ] ) on KTD’s features and lengthscales, without process noise. The observation variance of a target is a constant ϵ 0 \epsilon_0 ϵ 0 plus γ 2 ϕ ( x ′ , u ∗ ) ⊤ P t + 1 ϕ ( x ′ , u ∗ ) \gamma^2\phi(x',u^*)^\top P_{t+1}\phi(x',u^*) γ 2 ϕ ( x ′ , u ∗ ) ⊤ P t + 1 ϕ ( x ′ , u ∗ ) , the variance of the successor’s value at its greedy input under the next time step’s filter. This is the form of variance that § 3.3 argues against, here on a parametric model. We tune ϵ 0 \epsilon_0 ϵ 0 over { 10 − 4 , 10 − 3 , … , 1 } \{10^{-4}, 10^{-3}, \ldots, 1\} { 1 0 − 4 , 1 0 − 3 , … , 1 } , extended at the edges.
Deep RL. Table 5 lists the settings of the deep RL baselines. Observations and inputs are normalised to [ − 1 , 1 ] [-1, 1] [ − 1 , 1 ] with their bounds. DQN maximises over continuous inputs by L-BFGS-B on [ − 1 , 1 ] d u [-1,1]^{d_u} [ − 1 , 1 ] d u and Ensemble-DQN by projected gradient ascent with three restarts. Ensemble-DQN keeps each transition for each critic with probability 0.8, explores by the upper-confidence rule over the ensemble with coefficient β \beta β and is evaluated with the ensemble mean. On the reactor and biomass production SAC uses a target entropy scale of 0.5 and multiplies the reward by 50 to compensate for the sparse terminal reward.
Table 5. Settings of the deep RL baselines. Learning-rate grids are multiplied by { 1 / 3 , 1 , 3 } \{1/3, 1, 3\} { 1/3 , 1 , 3 } and extended at an edge as above.
Sparse HGPQ
This appendix introduces Sparse HGPQ, which replaces each exact GP of HGPQ by a sparse GP. It shows that Sparse HGPQ keeps the cost linear in the number of episodes without changing the algorithm, and that on the pendulum and target tracking it remains more sample-efficient than the deep RL methods when they need hundreds of episodes.
Sparse HGPQ. An exact refit after n n n episodes costs O ( n 3 ) O(n^3) O ( n 3 ) per time step, so for budgets of hundreds of episodes Sparse HGPQ replaces the GP of each time step by the sparse variational GP of Titsias [51 ] with m m m inducing inputs, here with the per-target variances λ t , i = σ r 2 + ω t ( z i ) \lambda_{t,i} = \sigma_r^2 + \omega_t(z_i) λ t , i = σ r 2 + ω t ( z i ) of
Section 3.3 in place of a single noise level. The posterior mean becomes
μ t ( z ) = κ m ( z ) ⊤ A − 1 ∑ i = 1 n κ m ( z i ) y i λ t , i , A = K m m + ∑ i = 1 n κ m ( z i ) κ m ( z i ) ⊤ λ t , i , (51) \mu_t(\mathbf{z}) = \boldsymbol{\kappa}_m(\mathbf{z})^\top A^{-1} \sum_{i=1}^{n} \frac{\boldsymbol{\kappa}_m(\mathbf{z}_i)y_i}{\lambda_{t,i}}, \qquad A = K_{mm} + \sum_{i=1}^{n} \frac{\boldsymbol{\kappa}_m(\mathbf{z}_i)\boldsymbol{\kappa}_m(\mathbf{z}_i)^\top}{\lambda_{t,i}}, \tag*{(51)} μ t ( z ) = κ m ( z ) ⊤ A − 1 i = 1 ∑ n λ t , i κ m ( z i ) y i , A = K mm + i = 1 ∑ n λ t , i κ m ( z i ) κ m ( z i ) ⊤ , (51)
where κ m ( z ) \boldsymbol{\kappa}_m(\mathbf{z}) κ m ( z ) holds the kernel between z \mathbf{z} z and the inducing inputs. Every target enters, weighted by 1 / λ t , i 1/\lambda_{t,i} 1/ λ t , i , but only the m × m m \times m m × m matrix A A A is inverted, so a refit costs O ( n m 2 ) O(nm^2) O ( n m 2 ) , and the exact posterior is recovered when the inducing inputs are the training inputs. The kernel hyperparameters maximise the collapsed lower bound of Titsias [51 ] with these variances, which are estimated from leave-one-out residuals as for the exact GP (Appendix § 8 ), and the inducing inputs are located by a pivoted Cholesky decomposition of the prior kernel matrix, which Burt et al. [11 ] show places them close to optimally. Everything else in Algorithm 1 is unchanged, and we use m = 256 m = 256 m = 256 unless stated otherwise.
Benchmarking. We make the benchmarks harder by multiplying the process noise of the pendulum, target tracking and the reactor by three and by ten, by controlling k k k independent pendulums at once, which enlarges the state–input pair z \mathbf{z} z to dimension d = 4 k d = 4k d = 4 k , and by lengthening the horizon of the pendulum over the same physical time, with T T T from 10 to 80 and time step 4 / T 4/T 4/ T . Every method keeps its settings of Appendix § 11 without tuning them again. We compare Sparse HGPQ with SAC, TD3, DDPG and Ensemble-DQN only, showing exact HGPQ for reference. Sparse HGPQ runs for 600 episodes and the deep RL methods for 2000. Each setting uses ten seeds.
Figure 5 and Figure 6 show the learning curves. Measured by the number of episodes needed to reach 90% of the way from the median initial return to the best final return, On the pendulum and target tracking Sparse HGPQ is the fastest method in every setting except target tracking at ten times the process noise, where SAC needs 31 episodes and Sparse HGPQ 35, and its advantage holds as the noise and the horizon grow. On the reactor, whose fluctuating rates make the return vary widely between episodes, Sparse HGPQ is level with or above the deep RL methods over its 600 episodes, but the best final returns come from deep RL after 2000 episodes. Within 600 episodes it reaches the level only at three times the noise, after about 500 episodes against about 800 for Ensemble-DQN, and at one and ten times the noise Ensemble-DQN, DDPG or SAC reach it within their 2000 episodes. The advantage narrows as the dimension d d d of the state–input pair grows, and with four pendulums Sparse HGPQ needs about 300 episodes and SAC about 900.
Figure 5. Mean greedy return against episodes with one, three and ten times the process noise. Sparse HGPQ uses 256 inducing points. HGPQ, with exact GPs, is shown for comparison. Both run for 600 episodes and the deep RL methods for 2000. Bands are 95% confidence intervals over ten seeds.
Figure 6. Mean greedy return against episodes. Top: k k k independent pendulums, with d = d x + d u = 4 k d = d_x+d_u = 4k d = d x + d u = 4 k , return summed over the pendulums. Bottom: the pendulum at horizons T = 10 T = 10 T = 10 to 80 80 80 , the same physical task with time step 4 / T 4/T 4/ T . Sparse HGPQ uses 256 inducing points and runs for 600 episodes. HGPQ, with exact GPs, is shown for comparison over 150 episodes. Bands are 95% confidence intervals over ten seeds.
Cost of the GP fit. Figure 7 shows the time per episode spent fitting the GPs over 600 episodes, for HGPQ and for Sparse HGPQ with 16 to 256 inducing points, both with a constant target variance σ r 2 + s κ max \sigma_r^2 + s \kappa_{\max} σ r 2 + s κ m a x , which leaves out the cost of the heteroscedastic estimate. The cost of HGPQ grows faster than linearly in the number of episodes, and that of Sparse HGPQ grows linearly. With 128 or 256 inducing points Sparse HGPQ reaches a final return close to that of HGPQ, and with fewer its return falls on the pendulum and on target tracking.
Figure 7. Top: time per episode spent fitting the GPs of HGPQ and of Sparse HGPQ with m m m inducing points. Bottom: final return after 600 episodes against the total fitting time, mean ± \pm ± standard error over three to ten seeds. The reactor runs use its version without the constraint penalty and the rate fluctuations.
Ablations
This appendix tests the use of the next time step’s uncertainty in the target variances, the link between the variances and their targets, the choice of the noise estimator, and the sensitivity to the floor σ r \sigma_r σ r and to exploration.
Posterior variance of the next time step. Table 7 compares HGPQ with two homoscedastic variances and with three variances that contain the posterior variance σ t + 1 2 ( x i , u i ∗ ) \sigma_{t+1}^{2}(x_i,u_i^*) σ t + 1 2 ( x i , u i ∗ ) of the next GP: HGPQ’s variance with σ t + 1 2 \sigma_{t+1}^{2} σ t + 1 2 added, the floor plus σ t + 1 2 \sigma_{t+1}^{2} σ t + 1 2 , and a tuned constant plus σ t + 1 2 \sigma_{t+1}^{2} σ t + 1 2 , all with HGPQ’s GP, exploration and settings and on the same seeds. Adding σ t + 1 2 \sigma_{t+1}^{2} σ t + 1 2 to HGPQ’s variance changes the final return by at most 5%, and significantly only on target tracking, where it lowers the final cost from 0.097 to 0.069. It lowers the mean return of the first fifty episodes on the pendulum and target tracking (paired t t t -test over seeds, p < 0.05 p < 0.05 p < 0.05 ) and leaves it unchanged within the noise on the reactor and biomass production. The floor plus σ t + 1 2 \sigma_{t+1}^{2} σ t + 1 2 , which gives each target the uncertainty of the next estimate but no estimate of its own error, is worse on the reactor and biomass production. A tuned constant plus σ t + 1 2 \sigma_{t+1}^{2} σ t + 1 2 , with s s s tuned on the grid of Appendix E, matches HGPQ’s final return on the pendulum and target tracking but not on the reactor and biomass production, and starts more slowly on the pendulum, the reactor and biomass production. On target tracking every variance without HGPQ’s estimate starts faster, but the homoscedastic ones end with a higher cost.
Table 7. Choices of target variance on HGPQ’s GP: final return after 150 episodes (top) and mean return over the first fifty episodes (bottom), in the units of each benchmark, mean and 95% interval over seeds. Bold: the best mean of each row and every entry whose interval overlaps its interval. Thirty seeds (fifty on the pendulum and target tracking), tuned constant thirty. On the pendulum and the reactor the tuned scale of the last column is s = 0 s = 0 s = 0 , so it equals the floor plus σ t + 1 2 \sigma_{t+1}^2 σ t + 1 2 .
Variances moved between targets. Two controls keep HGPQ’s variances but detach them from their targets, on twenty seeds paired with HGPQ, with the predictions recorded before the runs. Permuting the variances at random among the targets of each time step, which keeps their values, multiplies the final cost by 6.5 on the pendulum and by 3.2 on target tracking. Giving every target of a time step the geometric mean of its variances does less harm on both, and its effect on the pendulum is not significant.
Choice of the noise estimator. HGPQ estimates ω t \omega_t ω t with a heteroscedastic GP. A simpler choice is a single level ω t \omega_t ω t per time step, fitted by marginal likelihood together with the kernel. With a few hundred targets per time step and no repeated inputs, the kernel can then pass close to every target, and the fitted level falls towards its lower bound.
Table 8 compares the heteroscedastic estimate with this single level and with four alternatives on the reactor and biomass production, each with HGPQ’s rule λ t , i = σ r 2 + ω t ( z i ) \lambda_{t,i} = \sigma_r^2 + \omega_t(z_i) λ t , i = σ r 2 + ω t ( z i ) and settings. Every alternative lowers the final return on biomass production, and the single level, leave-one-out cross-validation and the full covariance also lower it on the reactor. The heteroscedastic estimate is the best on both benchmarks.
Table 8. Change of the final return after 150 episodes relative to the heteroscedastic estimate of § 3.3 , paired over seeds, mean and 95% interval, in % of HGPQ’s mean.
Floor and exploration. Figure 8 shows the sensitivity to the floor and to exploration. With HGPQ’s variances, one floor σ r = 10 − 3 \sigma_r = 10^{-3} σ r = 1 0 − 3 on every benchmark instead of the tuned values does not significantly change the final return on the reactor or the LMDP, lowers the final cost of the pendulum by a third, and leaves that of target tracking unchanged within its interval (paired over seeds). On biomass production the tuned value is already 10 − 3 10^{-3} 1 0 − 3 . Setting ϵ = 0 \epsilon= 0 ϵ = 0 does not significantly lower the final return on any benchmark, so ϵ = 0.1 \epsilon= 0.1 ϵ = 0.1 is a safeguard for the coverage that Theorem 1 needs rather than a tuned value.
Figure 8. Change of HGPQ’s final return after 150 episodes, paired by seed and in % of HGPQ’s mean, with one floor σ r = 10 − 3 \sigma_r = 10^{-3} σ r = 1 0 − 3 on every benchmark (left) and without uniform exploration (right), mean and 95% interval. On biomass production the tuned floor is already 10 − 3 10^{-3} 1 0 − 3 .
Additional results
Learning curves. Figure 9 shows the mean return against the number of episodes on each benchmark, in the units of each benchmark. Each curve ends at the end of its method’s budget. For x ≥ 0 x \ge0 x ≥ 0 they are 0.006 for HGPQ, 0.011 with one noise level and 0.147 with the floor alone in A, and 0.023, 0.105 and 0.163 in B. For x < 0 x < 0 x < 0 , where the step of V 1 ∗ V_1^{*} V 1 ∗ lies in B, they are 0.029, 0.035 and 1.26 in A, and 0.121, 0.098 and 0.110 in B.
Figure 9. Mean return of the greedy policy against episodes on each benchmark, with 95% confidence intervals over thirty seeds. Each seed’s curve is averaged over the last ten episodes, as in Figure 3 .