## 4 Online Learning of Repeated Games
### Online Learning of the SCBG Problem  
We focus on expected regret for the SCBG problem, the expected regret is defined as, over \(T\) time periods, the difference between the cumulative loss produced by the actual allocation strategy (represented as a complete path) and the cumulative loss produced by the best single action in hindsight. \[R_{T}=\mathbb{E}\bigg{[}\sum_{t=1}^{T}L(\hat{p}_{t})\bigg{]}-\min_{p\in S} \sum_{t=1}^{T}L(p) \tag{11}\]  
where \(p\) denotes a best single action and \(\hat{p}_{t}\) denotes the action chosen by the learner at time \(t\). Our goal is to minimize the expected regret. If there is \(R_{T}/T\to 0\) when \(T\to\infty\), we say that the corresponding algorithm can achieve regret minimization. The MAB problem is one of the classic online learning problems, and the solution to the SCBG problem can be inspired by the algorithm for solving the MAB problem. The representative algorithm for solving the MAB problem is the Exp3 algorithm [24; 25; 26; 27]. Exp3 is an exponentially weighted algorithm that concerns exploration and exploitation. The player chooses an action at a mixture of normalized weights with coefficient \(1-\gamma\) and uniformly distributed probability with coefficient \(\gamma\), then the expected regret is calculated in the process of repeated games, and the algorithm is effective if the growth trend of the cumulative regret gradually slows down. The construction process of Exp3 algorithm is shows as Figure 6.  
Figure 5: Schematic diagram of OSP problem represented by graph structure. For the SCBG problem, the author in [28] proposed the Exp3-OE algorithm based on DAG, which can realize the upper regret bound of \(\tilde{O}\Big{(}\sqrt{n^{2}(S_{r}+1)T\ln(P)}\Big{)}\), where \(P\) represents the number of paths in the DAG, but the algorithm still has room for improvement. We improved the performance of the Exp3-OE algorithm by re-proposing the Exp3-U algorithm. The improvements are mainly reflected in the following two aspects:  
* In the Exp3-OE algorithm, only the weight of the path when sampling the actions is considered, and it does not considers the exploration of other action with smaller weights. The trade-off between exploration and exploitation is critical in incomplete information games. In the early proposed algorithm of Exp3 [24], the rest actions assigned a fixed probability to maintain the exploration of other action with smaller weights. It has been proven that this kind of algorithm can achieve a better regret guarantee through rigorous mathematical theory. In the SCBG problem, the strategy space is very large, and the path with more weight in the current confrontation stage may not be the optimal strategy in the long run. Therefore, inspired by the type of the Exp3 algorithm, we propose a path sampling method that mixes weight ratio distribution and uniform distribution. It assigns a weight to the edge which belongs to the selected path based on the regret of it in the previous stage, and adds a uniform distribution to ensure that the algorithm tries all actions. Otherwise, the algorithm may miss an action that performs well in the long run. * We multiply the loss of the revealed edge by the distance coefficient \(d\) to cause the different edges (edges corresponding to allocation strategies) to have different losses. The Exp3-OE algorithm does not take this aspect into consideration, but broadly sets equal the loss of the revealed edge to the loss of the selected edge, which cannot reflect the advantages and disadvantages of a different edge. We improve it and conduct experiments to verify the effectiveness of our methods. Our Exp3-U algorithm is shown in Algorithm 2. We first explain some of the notation,  
\[ \begin{array}{l}\text{O}^{\prime}(e)=\{p\in\mathcal{P}:\exists e^{\prime}\in p,e^{\prime}\to e\},\forall e\in\mathcal{E}\\ \text{O}^{\prime}(p)=\{e\in\mathcal{E}:\exists e^{\prime}\in p,e^{\prime}\to e\},\forall p\in\mathcal{P}\end{array}