Stochastic Shortest Path to Cost-Sensitive Multiclass: Towards Better Regret Bounds II

In a previous post I introduced a consistent reduction of stochastic shortest path (SSP) without recourse to cost-sensitive multiclass classification (CSMC) and proved two bounds. The first bound was quadratic in the path length and linear in the average CSMC regret over the path space. This was useful in establishing the consistency of the reduction but was unsatisfying in that a reduction of SSP to regression suggests a linear dependence on the path length is possible. The second bound was linear in the path length and linear in the maximum CSMC regret over the path space. This was unsatisfying due to the maximum operator. Since I had a theorem which said that only the regret along the optimal paths contributed to the overall regret, I felt I could do better, but wasn't sure how because I don't know the optimal paths (that being the problem I'm trying to solve).

Fortunately additional improvements are possible. Langford pointed me to a paper called Policy Search by Dynamic Programming. Like my SSP to CSMC reduction, in this paper they build a finite horizon policy backwards, starting from the last time step and using the learned policy for the future to estimate continuation costs. However they also leverage a ``base distribution'', which is a guess about the distribution of states that a good policy induces at a particular time step. They then prove a bound on performance, which translated back into SSP specifically, is linear in the path length and the average CSMC regret over the vertices with respect to the base distribution, plus a term which is linear in the path length and linear in the divergence between the base distribution used and the actual distribution of states induced by the reference policy. So paraphrasing, with a reasonable guess about where the optimal paths are, one can end up with a reasonable policy by setting up the CSMC subproblem inputs with respect to these guesses.

Viewed in this fashion, my reduction is essentially using the uniform base distribution (i.e., considers each vertex at each step of the path to be equally likely). Any improvement on this distribution would presumably lead to improvement on the SSP task. Given my hypothesized setup (a set of historical graph realizations with edge costs), I could run a deterministic SSP solver on each historical instance to generate a set historical state visitations. While this is not the same distribution as the optimal policy (this technique optimizes the per-instance costs, not the conditional expected per-instance costs), it might be a better approximation than the uniform distribution.

Stochastic Shortest Path Reduction to Cost-Sensitive Multiclass: Towards Better Regret Bounds

The regret bound for the path grid reduction of stochastic shortest path (SSP) without recourse to cost-sensitive multiclass classification (CSMC) was useful for showing consistency of the reduction, i.e., that a minimum regret path choosing policy results from a minimum regret cost-sensitive multiclass classifier. However the bound felt too loose: in particular, the $O (n^2)$ scaling factor on the regret did not seem consistent with the direct reduction to regression, which had an $\sim n^{3/2}$ scaling factor. Intuitively, it feels like I should be able to reduce to regression via CSMC and up with the same bound, which suggests an $O (n)$ scaling factor for the CSMC reduction.

So I've been trying to come up with something along those lines. I don't have anything I'm super happy with, but here are some thoughts. First, here's a theorem that says that the conditional SSP regret is bounded by the conditional cost-sensitive regret summed across subproblems encountered on the SSP regret minimizing path.

Theorem:Optimal Path Regret Bound

For fixed $x$, let $p^* (x)$ denote the set of $(k, v)$ pairs encountered on the SSP regret minimizing path of length $n$ from source vertex $s$ to target vertex $t$. Then for all SSP distributions and all cost-sensitive classifiers $\Psi$, \[ r_{spath} (\Psi) = E_{x \sim D_x} \left[ \sum_{(k, v) \in p^* (x)} q_{kv} (\Psi | x) \right], \] with the definition $\forall v, q_{n-1,v} (\Psi | x) = q_{nv} (\Psi | x) = 0$.

Proof: Let $\Upsilon^*_{kv} (x)$ be the set of $(k, v)$ pairs encountered on the SSP regret minimizing path of length $n - k$ from source vertex $v$ to target vertex $t$. Proof is inductive on the property $r_{kv} (\Psi | x) \leq \sum_{(k^\prime,v^\prime) \in \Upsilon^*_{kv} (x)} q_{kv} (\Psi | x)$.

When $k = n - 2$, it is easily verified directly that $r_{n-2,v} (\Psi | x) = q_{n-2,v} (\Psi | x)$.
For $k \in [1, n - 2)$, \[ \begin{aligned} r_{kv} (\Psi | x) &\leq q_{kv} (\Psi | x) + r_{k+1,w^*} (\Psi | x) \\ &\leq q_{kv} (\Psi | x) + \sum_{(k^\prime, v^\prime) \in \Upsilon^*_{k+1,w^*} (x)} q_{k^\prime,v^\prime} (\Psi | x) \\ &= \sum_{(k^\prime, v^\prime) \in \Upsilon^*_{kv} (x)} q_{k^\prime, v^\prime} (\Psi | x), \end{aligned} \] where the first step is from the next step bound lemma, the second step leverages the induction hypothesis, and the third step is the from definition of $\Upsilon^*_{kv} (x)$. Noting that $\Upsilon^*_{1s} (x) = p^* (x)$ yields
\[ r_{spath} (\Psi | x) = r_{1s} (\Psi | x) \leq \sum_{(k, v) \in p^* (x)} q_{kv} (\Psi | x). \]
Taking expectation with respect to $D_x$ completes the proof.

This theorem is interesting to me for two reasons. First it involves a sum over $n$ regrets, so it seems closer to a better bound; more about that further below. Second it indicates that really only the classifiers along the optimal path matter; the important ones change as $x$ varies, and I don't know apriori which ones they are (that would be the solution to SSP I seek!), but nonetheless many of the subproblems being solved are irrelevant. Maybe there is a way to iteratively adjust the cost vectors to take this into account.

Returning to the question of a better bound, it's a short hop from the above theorem to the statement \[ r_{spath} (\Psi) \leq (n - 2) E_{x \sim D_x} \left[ \max_{kv}\; q_{kv} (\Psi | x) \right], \] which has the right flavor. For instance, if I reduce the individual CSMC subproblems to regression, I'd pick up an extra $\sqrt{2n}$ leading factor and a $\sqrt{\epsilon_{kv}}$ dependence on the regression regret for the subproblem. That would give \[ \begin{aligned} r_{spath} (\Psi) &\leq (n - 2) E_{x \sim D_x} \left[ \max_{kv}\; q_{kv} (\Psi | x) \right] \\ &\leq (n - 2) \sqrt{2 n} E_{x \sim D_x} \left[ \max_{kv}\; \sqrt{\epsilon_{kv} (\Psi | x)} \right] \\ &\leq (n - 2) \sqrt{2 n} \sqrt{ E_{x \sim D_x} \left[ \max_{kv}\; \epsilon_{kv} \right]} \end{aligned} \] where $\max_a\; \sqrt{f_a} = \sqrt{\max_a\; f_a}$ and Jensen's inequality combine in the last step. This somewhat looks like $O (n^{3/2}) \sqrt{\epsilon}$ that I get from a direct reduction to regression. However I'm not satisfied, because I don't have a good intuition about how the expectation of a single regression subproblem relates to an ``$L^{\infty}$ style'' expectation over the maximum of a set of regression subproblems.

Stochastic Shortest Path: Consistent Reduction to Cost-Sensitive Multiclass

In previous posts I

1. introduced my quest to come up with alternative decision procedures that do not involve providing estimates to standard OR algorithms;
2. motivated understanding stochastic shortest path (SSP) without recourse as part of my quest and analyzed a reduction to regression;
3. described an error transform of SSP to cost-sensitive multiclass classification (CSMC) based upon Searn.
4. noted that a naive reduction of SSP to CSMC, composed with the filter tree reduction of CSMC to binary classification, suggested that an efficient consistent reduction of SSP without recourse to CSMC was possible.

I recommend visiting those posts to understand my notation (which is admittedly in flux) and the exact variant of SSP being considered.

Now I present a reduction of SSP to CSMC which is inspired by the filter tree. This reduction is consistent, i.e., achieving zero regret on the induced CSMC problem implies achieving zero regret on the original SSP problem.

The Algorithm Unlike the Searn-style approach, here I train the classifiers ``last-to-first''. As noted in a previous post, this is only possible because this is SSP without recourse, therefore the continuation costs do not depend upon the path prefix; in SSP with recourse, costs are revealed during traversal, and therefore continuation costs do depend upon the path prefix.

At each stage of training, I am learning paths from any vertex to the target vertex of a particular length. Initially the length is 1, so there is only one possible path from any vertex to the target vertex, and no learning is required. To learn paths of length $k$, I use the previously learned classifiers for paths of length $k-1$ to define the continuation costs of choosing a particular first step from a particular vertex. Once I reach paths of length $n$, I am done. This formulation leverages the simplification from a previous post where every node has a self-connection of zero cost and paths must be of length $n$. As a final post-processing step, I can remove any cycles in the path to get paths of any length up to $n$.

Algorithm:Path Grid Train

Data: Fully connected graph with $n$ vertices; target vertex $t$; source vertex $s$.
Data: Training data set $S$.
Input: Cost-sensitive classification routine $\mbox{Learn}$.
Result: Trained classifiers $\{\Psi_k | k \in [1, n-2] \}$.

1. Define $\gamma_{n-1, v} = \{ \{v, t\} \}$ for $v \in [1, n]$.
2. For each step $k$ in the path from $n - 2$ to 1:
   
   1. $S_k = \emptyset$.
   2. Let $\{ \gamma_{k+1,v} | v \in [1, n] \}$ be the predicted best paths of length $n - k - 1$ to the target vertex $t$ starting from vertex $v$.
   3. For each example $(x, f) \in S$:
      
      1. For each vertex $v$ from 1 to $n$; or when $k = 1$, only $v = s$:
         
         1. Define the estimated cost of continuing through vertex $w$ as $c_w (k, v) = f (e_{vw}) + \sum_{e \in \gamma_{k+1,w}} f (e)$.
         2. Define the lowest cost as $w^* (k, v) = \operatorname{arg\,min\,}_w c_w (k, v)$.
         3. $S_k \leftarrow S_k \cup \left\{\bigl( (x, v), w^* (k, v), c_w (k, v) \bigr) \right\}$.
      2. Let $\Psi_k = \mbox{Learn} (S_k)$.
      3. Let $\gamma_{k,v} = \Psi_k (x, v) \odot \gamma_{k+1,\Psi_k (x, v)}$.
3. Return $\{ \Psi_k | k \in [1, n-2] \}$.

To use classifiers on a novel example, I fold the predictors starting at the source vertex $s$; I stop one step early and force the last step to be to the target vertex $t$. In reality I would remove any cycles in the generated path, but for simplicity of analysis I will leave them in.

Algorithm:Path Grid Test

Data: Fully connected graph with $n$ vertices; target vertex $t$; source vertex $s$.
Data: Graph realization $x$.
Result: Path $\pi: X \to V^n$.

1. $\pi_1 (x) = s$.
2. $\pi_n (x) = t$.
3. $\pi_{k+1} (x) = \Psi_k (x, \pi_k (x))$.
4. In practice, remove any cycles in $\pi$; for analysis, leave them in.

Analysis My goal is to bound the shortest path regret \[ r_{spath} (\Psi) = E_{x \sim D_x} \left[ E_{f \sim D_{f | x}} \left[ \sum_{k=1}^{n-1} f (e_{\pi_k, \pi_{k+1}}) \right] - \min_{p \in P}\; E_{f \sim D_{f | x}} \left[ \sum_{e \in p} f (e) \right] \right], \] where $\pi: X \to V^n$ is given by the ``Path Grid Test'' algorithm. (This regret definition is slightly different from previous posts' convention, first because the path is defined as a sequence of vertices rather than a sequence of edges, and second because the path must be of length $n$. I've also introduced the notation $e_{ab}$ to represent the edge between vertices $a$ and $b$.)

I would like to bound it in terms of the cost-sensitive regret on the induced subproblems, and following a trick from the filter tree derivation, I will collapse the multiple subproblems into a single subproblem by defining an induced distribution as follows. Let $D = D_x \times D_{f|x}$ be the distribution of $(x, f)$. Define the induced distribution $D^\prime_\Psi$ of cost-sensitive examples $(x^\prime, c)$ as follows:

1. Draw $(x, f)$ from $D$.
2. Draw $k$ uniform on $[1, n - 2]$.
3. If $k = 1$, $v = s$; else draw $v$ uniform on $[1, n]$.
4. Let $x^\prime = (x, k, v)$.
5. Let $c_w (k, v) = f (e_{vw}) + \sum_{e \in \gamma_{k+1,w}} f (e)$ for $w \in [1, n]$.
6. Create cost-sensitive example $\bigl( x^\prime, c \bigr)$.

Note $D^\prime_\Psi$ depends upon the classifier via the continuation costs, hence the subscript. Ultimately I'd like to relate the shortest-path regret $r_{spath} (\Psi)$ to the induced cost-sensitive regret \[ \begin{aligned} q (\Psi) &= E_{x^\prime \sim D^\prime_{\Psi,x}} \left[ E_{c \sim D^\prime_{\Psi,c|x}} \left[ c_{\Psi_k (x, v)} (k, v) \right] - \min_w\; E_{c \sim D^\prime_{\Psi,c|x}} \left[ c_w (k, v) \right] \right] \\ &= \frac{1}{1 + n (n - 3)} \left( q_{1s} (\Psi) + \sum_{k=2}^{n-2} \sum_{v=1}^n q_{kv} (\Psi) \right), \end{aligned} \] where \[ \begin{aligned} q_{kv} (\Psi) &= E_{x \sim D_x} \left[ q_{kv} (\Psi | x) \right], \\ q_{kv} (\Psi | x) &= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv} (x)} f (e) \right] - \min_w\; E_{f \sim D_{f|x}} \left[ f (e_{vw}) + \sum_{e \in \gamma_{k+1,w} (x)} f (e) \right]. \end{aligned} \] It will be useful to talk about $r_{kv} (\Psi | x)$, the shortest-path regret for paths $P_{kv}$ of length $n - k$ starting at vertex $v$ and ending at vertex $t$, \[ r_{kv} (\Psi | x) = E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv}} f (e) \right] - \min_{p \in P_{kv}}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right]. \] Note by definition $r_{spath} (\Psi) = E_{x \sim D_x} [ r_{1s} (\Psi | x) ]$. I can relate $r_{kv} (\Psi | x)$ to $q_{kv} (\Psi | x)$, in a manner analogous to the filter tree derivation.

Lemma:Next Step Bound

Let $w^*$ be the first vertex in a regret minimizing path \[\underset{p \in P_{kv}}{\operatorname{arg\,min\,}} E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right].\] Then for all $(k, v) \in \{ (1, s) \} \cup \{ (k^\prime, v^\prime) | k^\prime \in [2, n - 2], v^\prime \in [1, n] \}$, either

1. $r_{kv} (\Psi | x) = r_{k+1,w^*} (\Psi | x)$ if $\Psi_k (x, v) = w^*$; or
2. $r_{kv} (\Psi | x) \leq q_{kv} (\Psi | x) + r_{k+1,w^*} (\Psi | x)$ if $\Psi_k (x, v) \neq w^*$.

Proof: First suppose that $\Psi_k (x, v) = w^*$. Then \[ \begin{aligned} r_{kv} (\Psi | x) &= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] - \min_{p \in P_{k+1,w^*}}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right] \\ &= r_{k+1,w^*} (\Psi | x). \end{aligned} \] Next suppose that $\Psi_k (x, v) \neq w^*$. Then \[ \begin{aligned} r_{kv} (\Psi | x) &= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv}} f (e) \right] - \min_{p \in P_{kv}}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right] \\ &= E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv}} f (e) \right] - E_{f \sim D_{f|x}} \left[ f (e_{vw^*}) + \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] \\ &\quad + E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] - \min_{p \in P_{k+1,w^*}}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right] \\ &\leq E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{kv}} f (e) \right] - \min_w\; E_{f \sim D_{f|x}} \left[ f (e_{vw}) + \sum_{e \in \gamma_{k+1,w}} f (e) \right] \\ &\quad + E_{f \sim D_{f|x}} \left[ \sum_{e \in \gamma_{k+1,w^*}} f (e) \right] - \min_{p \in P_{k+1,w^*}}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right] \\ &= q_{kv} (\Psi | x) + r_{k+1,w^*} (\Psi | x). \end{aligned} \]

Armed with this lemma I can easily prove the following theorem.

Theorem:Regret Bound

For all SSP distributions $D$ and all cost-sensitive classifiers $\Psi$, \[r_{spath} (\Psi) \leq (1 + n (n - 3)) q (\Psi).\]Proof: Consider a fixed $x$. Proof is by induction on $r_{kv} (\Psi | x) \leq \sum_{(k^\prime,v^\prime) \in \Omega_{kv}} q_{k^\prime,v^\prime} (\Psi | x)$, where $\Omega_{kv} = \{ (k, v) \} \cup \{ (k^\prime, v^\prime) | k^\prime \in [k + 1, n - 2], v^\prime \in [1, n] \}$ is the set of path-length and vertex pairs that are in any path starting at $(k, v)$.

When $k = n - 2$, it is easily verified directly that $r_{n-2,v} (\Psi | x) = q_{n-2,v} (\Psi | x)$. For $k \in [1, n - 2)$, \[ \begin{aligned} r_{kv} (\Psi | x) &\leq q_{kv} (\Psi | x) + r_{k+1,w^*} (\Psi | x) \\ &\leq q_{kv} (\Psi | x) + \sum_{(k^\prime,v^\prime) \in \Omega_{k+1,w^*}} q_{k^\prime,v^\prime} (\Psi | x) \\ &\leq \sum_{(k^\prime,v^\prime) \in \Omega_{kv}} q_{k^\prime,v^\prime} (\Psi | x), \end{aligned} \] where the first step is from the lemma, the second step leverages the induction hypothesis, and the third step is due to the non-negativity of regret. The induction terminates at the root where \[ r_{1s} (\Psi | x) \leq \sum_{(k, v) \in \Omega_{1s}} q_{kv} (\Psi | x) = (1 + n (n - 3)) q (\Psi | x).\] Taking the expectation of both sides with respect to $D_x$ completes the proof.

Comparison with Regression Reduction The analysis of reduction of SSP with recourse to regression with $L_2$ loss yielded a $\sqrt{r}$ dependence on the regression regret with a scaling factor of $\sim n^{3/2}$. This reduction to CSMC yields a linear dependence on the CSMC regret but with a scaling factor of $O (n^2)$. Unfortunately then the bounds are not directly comparable.

If I further reduce CSMC to regression I end up with a $O (n^{5/2})$ scaling factor and $\sqrt{r}$ dependence on the regression regret. It intuitively feels like I should be able to reduce to regression via CSMC and get the same result as reducing to regression directly; that suggests that an $O (n)$ scaling factor is possible. I actually separated out the lemma from the theorem because I'm hoping to prove a tighter bound using the lemma (something involving $n$ quantities, rather than $n^2$); but that's for another day.

Stochastic Shortest Path via the Filter Tree: Ideas

In previous posts I talked about stochastic shortest path (SSP) with recourse and analyzed a reduction to regression and a reduction to cost-sensitive multiclass classification (CSMC) via Searn. The latter was underwhelming because it only led to a bound on the SSP regret in terms of the error on the underlying CSMC problems, whereas the regression reduction leads to a bound on the SSP regret in terms of the regret on the underlying regression. (See the previous posts on regression reduction and Searn-style reduction for a discussion of the exact variant of SSP analyzed and the notation used).

I have strong reason to believe that a reduction to CSMC with a bound based upon the underlying CSMC regret is possible. I haven't completely worked it out, but my inspiration comes from thinking about what a naive reduction of SSP to CSMC would look like.

First, some further simplifications over previous posts. As before, I'll require all paths to be of length $n$, but now I'll allow any node to connect to itself for zero cost (not just the target node). This means I can associate each potential path with an $(n - 2)$ digit number in base $n$. There an $n^{n-2}$ such paths, and a direct reduction to CSMC would equate each path with a class. With this naive reduction, the shortest path regret and the cost-sensitive regret are identical. Of course, I am ignoring a lot of the structure here, because these classes don't have independent costs: they are related because they are different sums over only $n^2$ quantities.

Since there are so many classes in this naive reduction, I'll choose the filter tree to reduce the CSMC to binary classification. It has the advantage that run-time computation is logarithmic in the number of classes, or $(n - 2) \log_2 (n)$, which actually looks reasonable. Training time is another story: I'll have to train $n^{n-2}$ binary classifiers at all of the internal nodes of the filter tree.

But wait, the filter tree let's me fix any tree over the labels. Suppose that $n = 2^m$ in what follows, so I don't have to think about parents that lack two children in the tree. I can choose a tree such that the $k^\mathrm{th}$ leaf is the $(n-2)$ digit base $n$ number whose value is $k$. In that case, at the first level of internal nodes, all paths being compared will share all but their last digit, so instead of having to learn $n^n / 2$ binary classifiers, I can just learn $n^2 / 2$ binary classifiers. This is because the cost of two paths that share all but their last digit depends only upon their last two digits and not the rest of the path prefix. (This is the important part, true only because this is SSP without recourse: if this were SSP with recourse, costs would be revealed as the paths were traversed, and the conditional distributions of remaining edge costs would be a function of the path). On the second level of internal nodes, I need only learn $n^2 / 4$ classifiers; and for the first $\log_2 (n)$ levels of internal nodes, I only need learn $n^2$ classifiers in total.

On the $(\log_2 (n) + 1)^\mathrm{th}$ level of internal nodes, paths that are being compared share all but their last three digits; and the last digit is determined by the second last digit via the lower levels of internal nodes. This means that for the next $\log_2 (n)$ levels of internal nodes, I still only have to learn $n^2$ classifiers in total.

Following this logic, I have to learn a total of $n^2 (n - 2) \log (n)$ binary classifiers at train time, and perform $(n - 2) \log (n)$ classifications at test time. The regret bound for the filter tree is the sum of the regrets of internal nodes, which suggests a $n^{n-2}$ leading factor, but because there are only $n^2 (n - 2) \log_2 (n)$ actual distinct internal nodes one might hope the regret would scale as the lower quantity.

Now I have to dig into the filter tree and really understand it, and translate this back into a specific reduction for SSP.

Stochastic Shortest Path via Searn

In a previous post I talked about Stochastic Shortest Path (SSP) without recourse and analyzed a reduction to regression (i.e., analyzed the strategy of estimating the edge costs and then using a standard deterministic shortest path solver on the estimates). The analysis was in terms of the regret of a shortest path chooser $h: X \to P$ mapping an edge realization $X$ to a (hopefully short) path $P$, \[ r_{spath} (h) = E_{x \sim D_x} \left[ E_{f \sim D_{f | x}} \left[ \sum_{e \in h (x)} f (e) \right] - \min_{p \in P}\; E_{f \sim D_{f | x}} \left[ \sum_{e \in p} f (e) \right] \right], \] where $D_x$ is the distribution of edges and $D_{f|x}$ the conditional distribution of edge costs given an edge realization (please see the previous post for a fuller description of the notation and a description of the precise variant of SSP analyzed).

I also noted that cost-sensitive multiclass classification (CSMC) looks like SSP on a shallow graph. This correspondence suggests that SSP could be attacked by reduction to a sequence of CSMC problems. The general correspondence between sequential decision problems and CSMC was explored theoretically by Langford and Zadrozny and exploited practically by Duame et. al. via the Searn algorithm. This reduction of SSP to CSMC is a special case of Searn.

In terms of my current obsession this reduction is very exciting, because it provides an alternative mechanism for solving a non-trivial problem in lieu of the intuitive ``let's estimate the coefficients and use a standard solver'' strategy. Whether this trick applies to more complicated problems I encounter, and whether it results in good solutions in practice, remains to be seen.

Optimal Substructure The (shortest path) journey of a thousand miles begins with a single (optimally shortest) step. In particular, given any starting vertex $s$, intermediate vertex $v$, and target vertex $t$, the shortest path $p^*_{st;v}$ from $s$ to $t$ that includes $v$ is related to the shortest path $p^*_{sv}$ between $s$ and $v$ and $p^*_{vt}$ between $v$ and $t$ via \[ p^*_{st;v} = p^*_{sv} \odot p^*_{vt}, \] where $\odot$ represents path concatenation. By taking $v$ to be the set of adjacent vertices to $s$, this suggests defining a cost-vector for the decision problem at vertex $s$ via \[ c (v; s, t) = f (\{ s, v \}) + \min_{p_{vt} \in P_{vt}}\; \sum_{e \in p_{vt}} f (e) - \min_{p_{st} \in P_{st}}\; \sum_{e \in p_{st}} f (e). \] Basically, the cost of choosing an edge at vertex $s$ is defined as the current edge cost plus the lowest total cost possible after traversing that edge, minus the lowest total cost starting at this vertex.

Since our variant of SSP always starts at the same starting vertex, it is clear how to kick this process off: for each training instance, compute the shortest path to the target from each vertex adjacent to the starting vertex, add the edge cost from the starting node, and use a favorite CSMC algorithm to produce a ``first-step'' policy. What about subsequent steps? A major insight of Langford and Zadrozny is that one can train the classifier for step $k+1$ by using the distribution of test instances induced by the sequence of classifiers learned for the first $k$ steps, i.e., sub-classifiers can be learned ``first-to-last''.

Regret Bound For simplicity of analysis I'll constrain all paths considered to be of length $n$; for shorter paths that might be encountered in practice, I can add a connection from the target node to itself of zero cost and force any path generation algorithm to include some number of self-connections at the target.

Let $\pi^{(n)}$ be the shortest path chooser defined by the composition of $n$ cost-sensitive classifiers, \[ \pi^{(n)} (X) = \bigodot_{k=1}^n \rho_k (X), \] where $\rho_k: (X, P_{k-1}) \to E$ is the $k^\mathrm{th}$ cost-sensitive classifier, which takes as input an edge realization and a path of length $k - 1$ from the start vertex, and outputs an edge which is the decided extension of the partial path. Consider the cost-sensitive error for a fixed graph realization $(x, f)$ and a fixed position $k$ in the generated path, \[ \epsilon_k (x, f) = f \left(\rho_k (x, \pi^{(k-1)} (x))\right) + \sum_{e \in \Psi_k (x, f)} f (e) - \sum_{e \in \Psi_{k-1} (x, f)} f (e) , \] where $\Psi_k (x, f)$ is the optimal extension of the path that connects the vertex chosen by $\rho_k$ to the target vertex, with $\Psi_0 (x, f)$ being the shortest path for the graph realization. If we sum this over all $k$ the last two terms telescope, and since $\Psi_n (x, f)$ is the empty path, we get \[ \sum_{k=1}^n \epsilon_k (x, f) = \sum_{e \in \pi^{(n)}} f (e) - \min_{p \in P}\; \sum_{e \in p} f (e). \] Taking the expectation of both sides with respect to $D_{f|x}$ yields \[ \begin{aligned} \sum_{k=1}^n E_{f \sim D_{f|x}} \left[ \epsilon_k (x, f) \right] &= E_{f \sim D_{f|x}} \left[ \sum_{e \in \pi^{(n)}} f (e) \right] - E_{f \sim D_{f|x}} \left[ \min_{p \in P}\; \sum_{e \in p} f (e) \right] \\ &\geq E_{f \sim D_{f|x}} \left[ \sum_{e \in \pi^{(n)}} f (e) \right] - \min_{p \in P}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right]. \end{aligned} \] Taking the expectation of both sides with respect to $D_x$ yields the bound \[ r_{spath} (\pi^{(n)}) \leq \sum_{k=1}^n E_{(x, f) \sim D} \left[ \epsilon_k (x, f) \right]. \] Thus regret on stochastic shortest path is bounded by the sum of the cost-sensitive error on each generated subproblem. Unfortunately since this is an error bound it is not directly comparable to the regret bound derived for reduction to regression.

Error bounds are less desirable than regret bounds, because the best possible error can be high on noisy problems making the bound vacuous. Is there a regret bound to be had here? Yes and no. If we define the cost-vector for the decision problem at vertex $s$ via \[ \tilde c (v; s, t) = f (\{ s, v \}) + \min_{p_{vt} \in P_{vt}}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p_{vt}} f (e) \right], \] then a similar argument to the above can show shortest path regret is identical to the sum of cost-sensitive regrets. Unfortunately computing $\tilde c$ would require a solution to SSP, which is what we seek. In Searn lingo, we have access to a good initial policy, but not the optimal initial policy.

Policy Iteration While we have a relationship between the regret of our path chooser and the error on the classification subproblems, improvement is possible: the cost vectors used in the subproblems are optimistic about the costs associated with each decision. In practice subsequent classifiers will make mistakes, both fundamentally because they do not have access to the edge cost information, and practically because we do not achieve the optimal cost-sensitive classifier at each step. Training earlier classifiers with costs that are sensitive to the types of errors subsequent classifiers will make should lead to improvement, but is chicken-and-egg: the cost-vectors define the classifiers, the classifiers define the policy, and the policy defines the cost-vectors. Training the subproblems ``last-to-first'' doesn't help, because earlier classifiers define the distribution of training samples for later classifiers, again leading to a circular dependence (and this strategy does not lend itself to analysis like ``first-to-last'' does).

One idea is to use the previous iteration of classifiers to define the continuation costs and then train another iteration, creating a sequence of path choosing functions that hopefully are improving. Searn adapts the framework of conservative policy iteration, which also uses the current policy to define continuation costs, but forms the next policy via interpolation between the old and new policies, which is more robust than just using the new policy. This interpolation is stochastic so we will switch to talking about path choosing policies.

Suppose we have a current path choosing policy $\psi: X \times E^* \to \mathbb{P} (E^*)$ $\ldots$ the notation is horribly broken here, but basically $\psi$ maps an edge realization and partial path to probability distribution over continuation paths to the target. Initially our $\psi$ will be the (deterministic) path choosing policy given by the sequence of cost-sensitive classifiers defined above. Given $\psi$ and a training instance $(x, f)$ we can generate cost-vectors for the decision problem for the $k^\mathrm{th}$ step via \[ c (x, \zeta) = f (\{ s, v \}) + E_{p \sim \psi (x, \zeta)} \left[ \sum_{e \in p} f (e) \right] - \min_v\; E_{p \sim \psi (x, \zeta \odot \{s, v\})} \left[ \sum_{e \in \{s, v\} \odot p} f (e) \right], \] where $\zeta$ (a partial path of length $k - 1$) is a random variable whose distribution is given by running the current policy over the training instance (we can realize this in practice via Monte-Carlo), $s$ is the terminal vertex of $\zeta$, and $v$ are the adjacent vertices to $s$. Training the set of cost-sensitive classifiers results in a new (deterministic) policy $\varphi$ which is combined with the existing policy via stochastic interpolation, \[ \psi_{new} = (1 - \beta) \psi + \beta \varphi, \] with $\beta \in [0, 1]$. Stochastic interpolation means using $\psi$ with probability $(1 - \beta)$ and using $\varphi$ with probability $\beta$. There is a choice of $\beta$ which comes with theoretical guarantees, but the Searn authors suggesting doing a line search in $[0, 1]$ for the best per-iteration $\beta$ (and stopping point for policy iteration) using a development set, i.e., a labelled set of data separate from that used to train the cost-sensitive classifiers. After $m$ training rounds we will end up with a policy of the form \[ \psi = \sum_m \alpha_m \pi^{(n)}_m, \] where $\alpha_m \geq 0$ and $\sum_m \alpha_m = 1$, i.e., at each step $k$ in the path we have probabilistic combination of cost-sensitive classifiers.


Non-Fully Connected Graphs To simplify the above discussion I assumed that graph realizations were fully connected. For a regression reduction, it is easy to see how to modify the strategy to account for non-fully connected graphs. First at train time, edges that are not feasible in the current realization are not incorporated into the training dataset. Second at test time, the argmax is restricted to range over only those edges that are feasible in the current realization. Feasibility here means both that the edge exists and that the vertex obtained by traversing it has a path to the target node within the remaining path length. Essentially the regressor attempts to learn the conditional expected cost of an edge given that it is feasible, and is only interrogated conditioned upon the edge being feasible. (Since this is SSP without recourse, the edge realization $X$ must contain explicit information about which edges are present or absent: there is no exploration and feedback with respect to the graph structure).

For this CSMC reduction the right way to proceed is less clear to me. If the graph structure is not fully connected but is fixed, there is no difficulty: simply use less classes in the CMSC classifier. The issue is when the graph structure is variable. One idea is to use a very large cost associated with edges that are infeasible, since a descent CSMC learner should learn the relationship between the ``edge feasibility features'' and a very large cost; if nonetheless an infeasible edge is chosen at test time, a random feasible edge could be substituted instead. If the graph connectivity structure consists primarily of a few cases, perhaps training multiple classifiers for each connectivity condition would be a good strategy. In that case, generalization to novel connectivity structures could be done by randomly picking a feasible edge; or perhaps these two strategies could be combined with the ``large cost'' training strategy being used as a fallback.

If the CSMC subproblems are themselves reduced to regression the same tricks can be used as in the direct reduction to regression to manage variable graph structure. This indicates a strength and weakness of reduction to regression: it solves a harder problem, namely, the ability to choose the best class out of any subset of allowed classes. In the case that one is only interested in the best class, this additional power is wasteful; and indeed when playing the role of the adversary, the regret bound for regression reduction is achieved by making the estimates of irrelevant classes perfect.

Stochastic Shortest Path: Reduction to Regression

The shortest path problem is a standard problem where, given a graph $G = (V, E)$, two vertices $s, t \in V$, and a cost function $f: E \to \mathbb{R}$, the problem is to find a path $P^*$ from $s$ to $t'$ satisfying \[ P^* = \underset{p \in P}{\operatorname{arg\,min\,}} \sum_{ e \in p } f (e).\] There is a natural linear programming formulation of the shortest path problem which looks like a minimum cost flow problem without capacity constraints, so it relates to my current obsession.

In OR, a solution to the shortest path problem involves efficiently computing the minimum cost path given the graph and the cost function. From a machine learning standpoint, however, we don't know the costs. Instead we know a current realization of the graph and have some historical data about what the costs were on graphs encountered in the past. The OR community calls this (a variant of) the Stochastic Shortest Path problem.

The Setup I'll define the Stochastic Shortest Path (SSP) problem as follows. For simplicity, I'll assume the following:

1. A fully connected graph structure with a fixed number of vertices $n$. One could imagine prohibitively large costs on edges as a vehicle for handling not fully connected graphs (or graphs with less than $n$ vertices).
2. Any cyclic path has non-negative weight almost surely. For instance, this is true if all the edge costs are non-negative.
3. We are always trying to get from vertex 0 to vertex $n - 1$, and $P$ is the set of (acyclic) paths that connect vertex 0 to vertex $n - 1$.

Also please note that $E$ represents the set of edges in the graph, but also represents the expectation operator. Hopefully this is clear from context.

Assume a distribution $D = D_x \times D_{f | x}$ from which graph instances are drawn i.i.d., where $D_x$ is a distribution over edge realizations $X = E^{n \choose 2}$ and $D_{f | x}$ is the distribution of edge costs given a particular edge realization. (The idea here is that our edges come with some associated features that we can use to help predict the best path.) A shortest path finder is a function $h: X \to P$ which takes the edge realization and returns a path. The regret of $h$ is \[ r_{spath} (h) = E_{x \sim D_x} \left[ E_{f \sim D_{f | x}} \left[ \sum_{e \in h (x)} f (e) \right] - \min_{p \in P}\; E_{f \sim D_{f | x}} \left[ \sum_{e \in p} f (e) \right] \right], \] i.e., the difference in cost between the path selected by $h$ and the optimal path. Solving SSP means taking set of $m$ data points sampled from $D^m$ and constructing a shortest path finder that has low regret.

The OR community calls this variant SSP without recourse, because the values of the arc costs are only known after the path is chosen. Other setups are possible, e.g., in the Canadian traveller problem the costs are revealed and charged as the graph is traversed and what is desired is a traversal policy.

Relation to Cost-Sensitive Multiclass I feel this is interesting because it represents a step beyond cost-sensitive multiclass classification (CSMC) into a more general OR problem, so it relates to my current obsession about understanding how to do machine learning whose output is used in a linear program.

Consider a network with a single starting node $s$, and single destination node $t$, and set of $K$ intermediate nodes indexed by $k$ with source costs $f (s, k)$ and with sink costs $f (k, t) = 0$. In this case all paths are of the form $\{ (s, k), (k, t) \}$ for some $k$ and the optimal path is $\{ (s, k^*), (k^*, t) \}$ where \[ k^* = \underset{k}{\operatorname{arg\,min\,}} f (s, k). \] Thus CSMC is a special case of SSP where the graph structure is constrained. Viewed in this way SSP looks like a multi-step version of CSMC which is ballistically planned, suggesting that a good understanding of SSP might yield insight into problems involving selecting a subset of classes from a set (e.g., populating a slate of $m$ advertisements when there are $n > m$ eligible advertisements).

As indicated previously, some state of the art approaches to CSMC do not reduce to regression. This suggests the possibility that the best way to attack SSP is not to estimate the costs and feed them to a standard shortest path finding algorithm. That sounds like a fun topic for another post. For now I'll assume we're solving the uncertain costs shortest path problem by estimating the costs and then using a standard shortest path finding algorithm.

The resulting error and regret bounds are very similar to those for CSMC, and the derivations are very similar, including an analogous one-sided loss that can be defined for SSP. In particular dependence on the error or regret of the underlying regression problem has the same exponent, but the leading constants are worse, e.g., the CSMC regret bound for $L^2$ loss scales as square root of the number of classes (corresponding to edges or squared vertices in a fully connected graph), but the SSP regret bound for $L^2$ loss scales as the number of vertices cubed to the same exponent. This is because the constrained graph structure of CSMC is relaxed in the fully connected SSP setting. Presumably more restrictive assumptions about the graph connectivity of the SSP instances could improve the leading constants.

Reduction to Regression A regression reduction for SSP is a function $g: E \to \mathbb{R}$ which defines an associated shortest path finder $h_g: X \to P$ via
\[ h_g (x) = \underset{p \in P}{\operatorname{arg\,min\,}} \sum_{ x_{ij} \in p } g (x_{ij}). \] In other words, we estimate the costs and then use a standard solver like Bellman-Ford. We would like to bound $r_{spath}$ in terms of either error on the underlying regression problem,
\[ \nu_L (g) = E_{(x, f) \sim D} \left[ \frac{1}{|x|} \sum_{e \in x} L (g (e), f (e)) \right] , \] or the regret on the underlying regression problem \[ \epsilon_{L} (g) = \nu_{L} (g) - \min_g\; \nu_{L} (g). \] Note the fully connected assumption implies $|x| = {n \choose 2}$, but the above expression for the regression error intuitively feels like it could generalize to non-fully connected graphs.

Error bound for $L^q$ loss for $q \geq 1$ Consider an instance $(x, f)$ and suppose our regressor has cost estimates which differ from the actual costs by $\delta (e)$, \[ g (e) = f (e) + \delta (e). \] Imagine an adversary which attempts to create a certain amount of SSP regret on this instance while minimizing the amount of regression error on this instance. The adversary is faced with the following problem: \[ \begin{aligned} & \min_{\delta}\; \sum_{e \in x} L \bigl (f^* (e) + \delta (e), f (e) \bigr) \\ \mathrm{s.t.} \quad & \sum_{e \in h_g (x)} f (e) - \min_{p \in P}\; \sum_{e \in p} f (e) = r. \end{aligned} \] Clearly $r$ can only take one of $|P|$ values corresponding to the possible decisions made by $h_g$. Consider each such possible decision $p^{**}$. Then the adversary has a family of choices of the following form:
\[ \begin{aligned} & \min_{\delta}\; \sum_{e \in x} |\delta (e)|^q \\ \mathrm{s.t.} \; \forall p \neq p^{**}, \; & \sum_{e \in p^{**}} f (e) + \delta (e) \leq \sum_{e \in p} f (e) + \delta (e), \end{aligned} \] where we have substituted in $L^q (\hat y, y) = |y - \hat y|^q$ loss. For $q > 1$, the KKT stationarity condition implies \[ q\ \Theta (\delta (e))\ |\delta (e)|^{q - 1} + \sum_{p \neq p^{**}} (1_{e \in p^{**}} - 1_{e \in p}) \mu_p = 0. \] Complementary slackness indicates $\mu_p = 0$ unless the constraint for $p$ is active. Let $p^* = \operatorname{arg\,min\,}_{p \in P} \sum_{e \in p} f (e)$ be the true optimal path choice, in which case only $\mu_{p^*}$ need be non-zero. The stationarity condition simplifies to \[ q\ \Theta (\delta (e))\ |\delta (e)|^{q - 1} + (1_{e \in p^{**}} - 1_{e \in p^*}) \mu_{p^*} = 0, \] which is more clearly stated as \[ \delta (e) = \begin{cases} \alpha & \mbox{if } e \in p^* \mbox{ and } e \not \in p^{**} ; \\ -\alpha & \mbox{if } e \not \in p^* \mbox{ and } e \in p^{**} ; \\ 0 & \mbox{otherwise,} \end{cases} \] where $\alpha = (\mu_{p^*} / q)^{q - 1}$. Intuitively, since errors are penalized convexly, the adversary does best by concentrating equal and opposite error on those edges which are exclusively in either $p^{**}$ or $p^*$. Let $\kappa (p^*, p^{**}) = |p^*| + |p^{**}| - 2 |p^* \cap p^{**}|$. Substituting into the inequality constraint yields \[ \begin{aligned} \sum_{e \in p^{**}} f^* (e) - \sum_{e \in p^*} f^* (e) &\leq \sum_{e \in p^*} \delta (e) - \sum_{e \in p^{**}} \delta (e) \\ &= \kappa (p^*, p^{**}) \sqrt[q]{\frac{|x|}{\kappa (p^*, p^{**})} \frac{1}{|x|} \sum_{e \in x} |\delta (e)|^q} \\ &\leq (2 |V| - 2)^{1-1/q} \sqrt[q]{|x|} \sqrt[q]{\frac{1}{|x|} \sum_{e \in x} |\delta (e)|^q}, \end{aligned} \] where the last step leverages $\kappa (p^*, p^{**}) \leq 2 |V| - 2$. Taking expectation with respect to $D$ yields the result \[ \begin{aligned} r_{spath} (h_g) &\leq (2 |V| - 2)^{1-1/q} \sqrt[q]{|x|} \ E_{x \sim D} \left[ \sqrt[q]{\frac{1}{|x|} \sum_{e \in x} \delta (e)^q} \right] \\ &\leq (2 |V| - 2)^{1-1/q} \sqrt[q]{|x|} \sqrt[q]{\nu_{L^q} (g)}, \end{aligned} \] where the last step is due to Jensen's inequality. This is similar to the corresponding bound for CSMC, except the leading term is $\sim n^{1 + 1/q}$. The $\sqrt[q]{|K|}$ dependence for the CSMC error bound for $L^q$ loss might cause an apriori intuition of $\sim n^{2/q}$ (noting the correspondence between classes and edges). The additional $\sim n^{1 - 1/q}$ term is because in the constrained graph structure of CSMC, $\kappa (p^*, p^{**}) = 2$, i.e., independent of $n$.

Because the optimal adversarial $\delta$ is positive on $p^*$ and negative on $p^{**}$, the above bounds also apply for one-sided $L^q$ loss, defined as \[ L^q_{(1)} (\hat y, y) = \lfloor (2\ 1_{e \in p^*} - 1) (y - \hat y) |y - \hat y|^{q - 1} \rfloor, \] where $\lfloor x \rfloor = \max (x, 0)$. Under one-sided loss, underestimating the edge values on the optimal path is not penalized, and overestimating the edge values not on the optimal path is not penalized. Because $L^q_{(1)}$ loss is bounded above by $L^q$ loss, this loss function leads to an improved bound.

Taking $q \to 1$ (i.e., one-sided absolute loss) gives the best bound in this family, \[ r_{spath} (h_g) \leq |x| \nu_{L^1_{(1)}} (g), \] although it should be noted this derivation technique is not valid at $q = 1$ (KKT does not apply due to lack of continuous differentiability). However the bound can be shown valid at $q = 1$ directly.

Regret Bound for $L^2$ loss For deriving the regret bound, we relax the unnecessary degrees of freedom granted to the adversary in the error bound derivation. In particular, since the regressor is defined as a function of $x$ only, the adversary should not be allowed to pick a separate $\delta$ for each pair $(x, f)$.

Consider an edge realization $x$ with associated conditional edge cost distribution $D_{f | x}$, and suppose our regressor from a minimum error regressor's estimate $f^* (e)$ by $\delta (e)$, \[ g (e) = f^* (e) + \delta (e). \] Imagine an adversary which attempts to create a certain amount of SSP regret on this instance while minimizing the amount of regression regret on this instance. This adversary is faced with the following problem: \[ \begin{aligned} & \min_{\delta}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in x} L \bigl (f^* (e) + \delta (e), f (e) \bigr) - L \bigl (f^* (e), f (e) \bigr) \right] \\ \mathrm{s.t.} \quad & E_{f \sim D_{f|x}} \left[ \sum_{e \in h_g (x)} f (e) \right] - \min_{p \in P}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in p} f (e) \right] = r. \end{aligned} \] Clearly $r$ can only take one of $|P|$ values corresponding to the possible decisions made by $h_g$. Consider each such possible decision $p^{**}$. Then the adversary has a family of choices of the following form: \[ \begin{aligned} &\min_{\delta}\; E_{f \sim D_{f|x}} \left[ \sum_{e \in x} L \bigl (f^* (e) + \delta (e), f (e) \bigr) - L \bigl (f^* (e), f (e) \bigr) \right] \\ \mathrm{s.t.} \; \forall p \neq p^{**}, \; & \sum_{e \in p^{**}} f^* (e) + \delta (e) \leq \sum_{e \in p} f^* (e) + \delta (e). \end{aligned} \] For $L^2 (\hat y, y) = |y - \hat y|^2$ loss specifically, the objective function simplifies \[ \begin{aligned} & E_{f \sim D_{f|x}} \left[ \sum_{e \in x} L^2 \bigl (f^* (e) + \delta (e), f (e) \bigr) - L^2 \bigl (f^* (e), f (e) \bigr) \right] \\ &= \sum_{e \in x} 2 \delta (e) \left(f^* (e) - E_{f \sim D_{f|x}} [ f (e) ] \right) + \delta (e)^2 \\ &= \sum_{e \in x} \delta (e)^2, \end{aligned} \] since $f^*(e) = E_{f \sim D_{f|x}} [ f (e) ]$. Therefore the adversary's family of choices is given by \[ \begin{aligned} &\min_{\delta}\; \sum_{e \in x} \delta (e)^2 \\ \mathrm{s.t.} \; \forall p \neq p^{**}, \; & \sum_{e \in p^{**}} f^* (e) + \delta (e) \leq \sum_{e \in p} f^* (e) + \delta (e). \end{aligned} \] The KKT stationarity condition implies \[ 2 \delta (e) + \sum_{p \neq p^{**}} (1_{e \in p^{**}} - 1_{e \in p}) \mu_p = 0. \] Complementary slackness indicates $\mu_p = 0$ unless the constraint for $p$ is active. Let $p^* = \operatorname{arg\,min\,}_{p \in P} E_{f \sim D_{f|x}} [ \sum_{e \in p} f (e) ]$ be the true optimal path choice, in which case only $\mu_{p^*}$ need be non-zero. The stationarity condition simplifies to \[ 2 \delta (e) = (1_{e \in p^*} - 1_{e \in p^{**}}) \mu_{p^*}, \] which is more clearly stated as \[ \delta (e) = \begin{cases} \mu_{p^*} / 2 & \mbox{if } e \in p^* \mbox{ and } e \not \in p^{**} ; \\ -\mu_{p^*} / 2 & \mbox{if } e \not \in p^* \mbox{ and } e \in p^{**} ; \\ 0 & \mbox{otherwise.} \end{cases} \] Intuitively, since errors are penalized convexly, the adversary does best by concentrating equal and opposite error on those edges which are exclusively in either $p^{**}$ or $p^*$. Let $\kappa (p^*, p^{**}) = |p^*| + |p^{**}| - 2 |p^* \cap p^{**}|$. Substituting into the inequality constraint yields \[ \begin{aligned} \sum_{e \in p^{**}} f^* (e) - \sum_{e \in p^*} f^* (e) &\leq \sum_{e \in p^*} \delta (e) - \sum_{e \in p^{**}} \delta (e) \\ &= \kappa (p^*, p^{**}) \sqrt{\frac{|x|}{\kappa (p^*, p^{**})} \frac{1}{|x|} \sum_{e \in x} \delta (e)^2} \\ &\leq \sqrt{2 |V| - 2} \sqrt{|x|} \sqrt{\frac{1}{|x|} \sum_{e \in x} \delta (e)^2}, \end{aligned} \] where the last step leverages $\kappa (p^*, p^{**}) \leq 2 |V| - 2$. Taking expectation with respect to $D_x$ yields the result \[ \begin{aligned} r_{spath} (h_g) &\leq \sqrt{2 |V| - 2} \sqrt{|x|} \ E_{x \sim D_x} \left[ \sqrt{\frac{1}{|x|} \sum_{e \in x} \delta (e)^2} \right] \\ &\leq \sqrt{2 |V| - 2} \sqrt{|x|} \sqrt{\epsilon_{L^2} (g)}, \end{aligned} \] where the last step is due to Jensen's inequality. The regret bound is square root in the regression regret, with a scaling factor of $\sim n^{3/2}$. This is a bit worse than what might be expected apriori, since from the perspective of CSMC being SSP on a constrained graph structure, the $\sqrt{|K|}$ dependence for the $L^2$ regression regret bound for CSMC might inspire an apriori intuition like $\sim n$ (noting the correspondence between classes and edges). The additional $n^{1/2}$ is because in the constrained graph structure of CSMC, $\kappa (p^*, p^{**}) = 2$, i.e., independent of $n$.