## 4 Online Learning of Repeated Games
### Online Learning of the SCBG Problem
 \tag{12}\]  
where \(\text{O}^{\prime}(e)\) represents the set of paths that reveal the loss of edge \(e\), and \(\text{O}^{\prime}(p)\) represents the set of edges whose loss is revealed by path \(p\). Specifically, in Figure 5, if the player fails at stage1, edge2 can reveal the loss of edge1 and edge0 because it represents fewer resources than the selected allocation strategy by the player(the red path represents the allocation strategy chosen by the player). If it wins at stage1, edge2 can reveal the loss of edge3, which is 0, because it represents more resources than the selected allocation strategy; this is the definition of side observation. Through the information obtained from side observation, we can more accurately estimate the loss of some edges, then reasonably update the weights of the corresponding edges, and actions are chosen based on edge weights in the next confrontation. Figure 6: Schematic diagram of construction process of the Exp3 algorithm. ```
0:\(n\), \(S_{r}\), \(S_{m}\), \(T\), graph DAG Output: cumulative loss \(L(p)\) of SCBG
1: Initialize: \(w^{1}(e)=1\), \(\forall e\in\mathcal{E}\), \(L(p)=0\)
2:for\(t=1,2,\ldots,T\)do
3: Adversaries play (unobserved by the learner);
4: Use Algorithm 3 to sample a path \(p^{t}\);
5: Suffer and observe the loss \([\ell^{t}(e_{1}),\ell^{t}(e_{2}),\ldots,\ell^{t}(e_{n})]\) and \(L^{t}(p^{t})=\sum\limits_{e\in p^{t}}\ell^{t}(e)\) ;
6:\(L(p)=L(p)+L^{t}(p^{t})\);
7: Compute estimation of edges' loss \(\hat{\ell}^{t}(e)=d(e)*\ell^{t}(e)\mathrm{I}_{\{e\in\mathrm{O}^{t}(p^{t})\}}/(q ^{t}(e)+\chi)\), \(\forall e\in\mathcal{E}\);
8: where \(d(e)\) is the difference between the action represented by \(e\) (\(\forall e\in\mathrm{O}^{t}(p^{t})\)) and the action represented by the selected edge \(e^{\prime}\) (\(e^{\prime}\in p^{t}\)). 9:\(q^{t}(e)=\sum\limits_{p\in\mathrm{O}^{t}(e)}x^{t}(p)\) is computed by Algorithm 4;
10: Update weight \(w^{t+1}(e):=w^{t}(e)\cdot e^{-\gamma\hat{\ell}^{t}(e)}\);
11:endfor
```  
**Algorithm 2** Exp3-U Algorithm for SCBG problem, based on (Ref. [28], Algorithm 1)  
```
0:\(n\), \(t\in[T]\), \(w^{t}_{e}\), \(\forall e\in\epsilon\), graph DAG
1: Initialize: \(Q=\{0\}\), \(u_{0}=S\), and \(k=0\), D represent the terminal vertex;
2:for\(k\leq n\)do
3: Sample a node \(u_{k+1}\) from \(C(u_{k})\) with probability \((1-\gamma)\frac{w^{t}_{\{u_{k}\}_{k+1}\}H^{t}(u_{k+1},D)}{H^{t}(u_{k},D)}+\frac {\gamma}{S_{r}+1}\), where \(C(u_{k})\) is the vertex of the next layer in DAG, \(S_{r}\)( or \(S_{m}\)) is the budgets of \(\mathbf{r}\) (or m), \(H^{t}(u,v)=\sum\limits_{p\in\mathcal{P}_{u_{k}}}\prod\limits_{e\in p}w^{t}(e)\) represents the sum of the weights of all paths from vertex \(u\) to vertex \(v\) (the weight of a path is the product of the weights of all edges on the path);
4: Add \(u_{k+1}\) to the set \(Q\);
5:endfor
6:Output: \(p^{t}\in\mathcal{P}\) going through all nodes in \(\mathrm{Q}\). ```  
**Algorithm 3** WP Algorithm for path sample, based on (Ref. [28], Algorithms 3 and 4)  
When estimating the loss, we multiply the loss of the selected edge by the distance coefficient \(d\) and assign it to the loss of the revealed edge, so that different edges (edges corresponding to allocation strategies) have different losses. Our Exp3-U algorithm can achieve the upper regret bound of \(\tilde{O}\Big{(}\sqrt{n^{2}(S_{r}+1)T\ln(P)}\Big{)}\). And the proof process refers to the general regret upper bound proof process of [28; 29]. The following Algorithm 3 is the path sampling algorithm adopted in step 4 of the Exp3-U algorithm, which is called the WP algorithm in [28], we change it to be the method that mixes weight ratio distribution and uniform distribution.