{'fraction_non_alphanumeric': 0.04085798982045976, 'fraction_numerical': 0.015940488841657812, 'mean_word_length': 4.1585401038661285, 'pattern_counts': {'":': 0, '<': 4, '<?xml version=': 0, '>': 8, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 12, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Risk-Averse No-Regret Learning in Online Convex Games

We consider an online stochastic game with risk-averse agents whose goal is to learn optimal decisions that minimize the risk of incurring significantly high costs. Specifically, we use the Conditional Value at Risk (CVaR) as a risk measure that the agents can estimate using bandit feedback in the form of the cost values of only their selected actions. Since the distributions of the cost functions depend on the actions of all agents that are generally unobservable, they are themselves unknown and, therefore, the CVaR values of the costs are difficult to compute. To address this challenge, we propose a new online risk-averse learning algorithm that relies on one-point zeroth-order estimation of the CVaR gradients computed using CVaR values that are estimated by appropriately sampling the cost functions. We show that this algorithm achieves sub-linear regret with high probability. We also propose two variants of this algorithm that improve performance. The first variant relies on a new sampling strategy that uses samples from the previous iteration to improve the estimation accuracy of the CVaR values. The second variant employs residual feedback that uses CVaR values from the previous iteration to reduce the variance of the CVaR gradient estimates. We theoretically analyze the convergence properties of these variants and illustrate their performance on an online market problem that we model as a Cournot game.


Introduction
Online convex optimization (OCO) aims at solving optimization problems with unknown cost functions using only samples of the cost function values. Many practical applications can be modeled as OCO problems spam filtering (Hazan, 2019) and portfolio management (Hazan, 2006), among many others (Shalev-Shwartz et al., 2011). Oftentimes, OCO problems involve multiple agents interacting with each other in the same environment; for instance, in traffic routing (Sessa et al., 2019) and economic market optimization (Shi & Zhang, 2019), agents cooperate or compete, respectively, by sequentially selecting the best decisions that minimize their expected accumulated costs. These problems can be formulated as online convex games (Shalev-Shwartz & Singer, 2006;Gordon et al., 2008), and constitute the focus of this paper.
Typically, the performance of online optimization algorithms is measured using different notions of regret (Hazan, 2019), that capture the difference between the agents' online decisions and the optimal decisions in hindsight. An online algorithm is said to be no-regret (no-external-regret) if its regret is sub-linear in time (Gordon et al., 2008), i.e., if the agents are able to eventually learn the optimal decisions. Many no-regret algorithms have been proposed and analyzed for online convex games including (Shalev-Shwartz & Singer, 2006;Gordon et al., 2008;Hazan, 2019;Shalev-Shwartz et al., 2011). Common in these problems is the objective of the agents to minimize their expected cost functions. However, in high-stakes applications, minimizing the expected cost alone is not sufficient; avoiding the worst case is equally important. For example, in portfolio management, investing in the assets that yield the highest expected return rate is not necessarily the best decision since these assets may also be highly volatile and result in severe losses. To control for such catastrophic events, appropriate risk-averse criteria need to be considered during optimization, such as the Sharpe Ratio (Sharpe, 1994) or Conditional Value at Risk (CVaR) (Artzner et al., 1999).
In this paper, we consider online convex games with riskaverse agents, whose goal is to minimize the CVaR values of their cost functions. Moreover, we assume that only bandit feedback in the form of the costs of selected actions is available to the agents to estimate their CVaR values. To the best of our knowledge, risk-averse learning in convex games has not been explored in the literature. Most closely related to the problem considered here is work on deterministic online convex games with bandit feedback, including (Bravo et al., 2018;Duvocelle et al., 2018;Tatarenko & Kamgarpour, 2018;Lin et al., 2020). Specifically, (Bravo et al., 2018) relies on tools from stochastic approximation theory to show that derivative-free methods for monotone and concave games converge to the Nash equilibrium with probability 1. This work is extended in (Duvocelle et al., 2018) to time-varying games. The authors in (Duvocelle et al., 2018) show that if the time-varying game converges, then the sequence of actions converges to the Nash equilibrium. Common in these works is that the cost functions are deterministic. As such, they cannot model risk in the presence of uncertainty. Methods for risk-averse learning have been investigated, e.g., in (Urpí et al., 2021;Kalogerias & Powell, 2019;Chow et al., 2017). Specifically, in (Urpí et al., 2021), a risk-averse offline reinforcement learning algorithm is proposed that exhibits better performance compared to risk-neural approaches for robot control tasks. In (Kalogerias & Powell, 2019), a zeroth-order method for mean-semideviation-based risk-averse learning is proposed. We note that, despite the importance of controlling risk in many applications, only a few works employ CVaR as a risk measure and still provide theoretical results, e.g., (Curi et al., 2019;Cardoso & Xu, 2019;Tamkin et al., 2019;Soma & Yoshida, 2020;Kalogerias, 2020). In (Curi et al., 2019), risk-averse learning is transformed into a zero-sum game between a sampler and a learner. Then, using an adaptive sampling strategy, the regret of this game is ana- lyzed. In (Tamkin et al., 2019), a sub-linear regret algorithm is proposed for risk-averse multi-arm bandit problems by constructing empirical cumulative distribution functions for each arm from online samples. Recently, (Kalogerias, 2020) has shown that CVaR learning problems subject to not necessarily convex loss functions can be solved as efficiently as their risk-neutral counterparts.
Compared to the literature discussed above, risk-averse learning for online convex games possesses unique challenges, including: (1) The distribution of an agent's cost function depends on other agents' actions, and (2) Using finite bandit feedback, it is difficult to accurately estimate the continuous distributions of the cost functions and, therefore, accurately estimate the CVaR values. To address these challenges, in this paper we use samples of the cost functions to learn an empirical distribution function (EDF) of the random costs. Then, using this EDF, the agents can estimate the CVaR values of their cost functions, and use these CVaR values to construct zeroth-order estimates of the CVaR gradients. By appropriately designing this sampling strategy, we show that with high probability, the accumulated error of the CVaR estimates is bounded, and the accumulated error of the zeroth-order CVaR gradient estimates is also bounded. As a result, our method achieves sub-linear regret with high probability. To further improve the regret of our method, we allow our sampling strategy to use previous samples to reduce the accumulated error of the CVaR estimates. Specifically, at time step t, we build the EDF estimate using samples from times t and t − 1, and then use this EDF to estimate the CVaR values and the corresponding CVaR gradients, as before. Assuming that the variation of the CDF of the cost function at two consecutive time steps is bounded by the distance between the two corresponding actions at these time steps, we theoretically show that the accumulated error of the CVaR estimates is strictly less than that achieved without reusing previous samples under certain conditions. We also provide an alternative way of improving the regret by utilizing residual feedback (Zhang et al., 2020a;b) that reduces the variance of the zeroth-order CVaR gradient estimates. We illustrate our method on an online market problem that we model as a Cournot game (Allaz & Vila, 1993).
To the best of our knowledge, this is the first work to address risk-averse learning in online convex games. Note that the CVaR value of each agent depends on the joint actions of all agents, hence the proposed risk-averse game is in essence a time-varying game as the agents update their actions sequentially. All existing literature on learning in games discussed before considers static games, except for (Duvocelle et al., 2018), that requires knowledge of whether the game converges and how the Nash equilibrium changes. However, the time-varying nature of the game considered here is due to the updates of the other agents and, therefore, it is not possible to know a prior whether this game will converge or not. As a result, the analysis in (Duvocelle et al., 2018) cannot be applied to analyze the game considered here. In addition, existing literature that employs zeroth-order techniques to solve learning problems in games typically relies on constructing unbiased gradient estimates of the smoothed cost functions. Nevertheless, unbiased gradient estimates cannot be obtained in risk-averse games since it is not possible to obtain accurate CVaR estimates of the cost functions merely using finite bandit feedback. Perhaps closest to the method proposed here is the approach in (Cardoso & Xu, 2019), that makes a first attempt to analyze risk-averse bandit learning problems. Using CVaR properties, the authors reformulate the CVaR optimization problem to an equivalent optimization problem of an augmented L function and show that the reformulated problem converges in the single-agent case. However, the analysis in (Cardoso & Xu, 2019) cannot be easily extended to multi-agent problems since minimizing the L functions is not equivalent to minimizing CVaR values in multi-agent games.
The rest of the paper is organized as follows. In Section 2, we define the proposed risk-averse online game and provide some assumptions. The main algorithm is presented in Section 3 with corresponding regret analysis. Two variants of this algorithm with improved regrets are provided in Section 4. In section 5, we use an online market example to illustrate the effectiveness of the proposed algorithms. Finally, we conclude this work in Section 6.

Problem Definition
We consider a repeated game G with N agents. At the beginning of each episode, each agent i ∈ N = {1, . . . , N } simultaneously chooses an action x i ∈ R di from a convex set X i and receives a random cost value that is sampled from the cost function J i (x i , x −i , ξ i ) : X × Ξ i → R, where x i is the action of agent i, x −i denotes the actions of agents except for agent i, X = Π N i=1 X i is the joint action space and ξ i ∈ Ξ i describes the uncertainty of the cost function.
Here we assume that the diameter of the convex set X i is bounded by D x for all i = 1, . . . , N . For ease of notation, we sometimes denote the cost function as is the concatenated vector of all agents' actions.
We use the Conditional Value at Risk (CVaR) as a risk measure to model the risk-aversion in the agents. Specifically, suppose that the random variable J i (x, ξ i ) has the CDF F x (y) = P{J i (x, ξ i ) ≤ y}. We drop the decision variable x in F x whenever it is clear from the contexts. Then, for a given risk level α i ∈ [0, 1], the CVaR of the cost function J i (x, ξ i ) of agent i at point x is defined as where J αi is the 1 − α i quantile of the distribution, which is also termed as Value at Risk (VaR). CVaR captures the average cost under the tail of the distribution of J i (x, ξ i ). Note that the CVaR value of the random variable J i (x, ξ i ) is determined its cumulative distribution function F , hence we sometimes write CVaR as a function of the CDF, i.e., CVaR αi [J i (x, ξ i )] = CVaR αi [F ] for ease of notation.
Here we assume that the agents have no prior knowledge about this game, i.e, the agents do not know the cost functions J i (x, ξ i ), and cannot observe the other agents' actions. The only information that is available to the agents is the cost of the selected actions. Moreover, we assume that the cost function J i (x, ξ i ) of each agent satisfies the following assumptions.
Given Assumptions 1 and 2, the below well known result characterizes important properties of the CVaR function. The proof can be found in (Cardoso & Xu, 2019). Lemma 1. Given Assumptions 1 and 2, we have that The objective of each agent i is to minimize its cumulative CVaR functions. Specifically, given a sequence of agents' actions {x t } T t=1 over T episodes, wherex t = (x i,t ,x −i,t ) denotes the agents' actual played actions at time step t, we define the regret (CVaR-regret) for agent i as which measures the cumulative loss against a best single policy in hindsight. Then, our goal in this paper is to design a no-regret (equivalently, sub-linear regret) algorithm to solve this game, such that lim T →∞ = 0 for all agents.

A Risk-Averse Learning Algorithm
In this section, we propose a risk-averse learning algorithm to solve the proposed online convex game. Our algorithm relies on a novel sampling strategy to estimate the CVaR values and a one-point zeroth-order estimator of the CVaR gradient. Specifically, since estimation of CVaR values requires the distribution of the cost functions which is impossible to compute using a single evaluation of the cost functions per time step, we assume that the agents can sample the cost functions multiple times to learn their distributions. For this, we introduce a practical sampling strategy described below.
During each time step t, the agents keep their actions fixed and draw n t samples of their individual cost functions. Then, they use these samples to determine their actions for time step t + 1 and then sample again. The sampling strategy is defined as where · is the ceiling function, T is the time horizon, U is the cost function bound as in Assumption 1, and a, b ∈ (0, 1) are parameters to be selected later. The parameters a, b are assumed to be known by all the agents beforehand so that the game is synchronous. Moreover, since a < 1, the number of samples n t will decrease with the iterations and eventually equal to 1.
The proposed risk-averse learning algorithm for online convex games is illustrated in Algorithm 1. At time step t, the agents randomly perturb their current actions x i,t by an amount δu i,t , where u i,t ∈ S di is a random perturbation direction sampled from a unit sphere S di ⊂ R di and δ is the size of this perturbation. Then, using the sampling strategy defined above, the agents play their perturbed actionŝ x i,t = x i,t + δu i,t for n t times, and obtain n t samples of their cost functions. For agent i, at time step t, we denote Algorithm 1 Risk-averse learning Require: Initial value x 0 , step size η, parameters a, b, δ, T , risk level α i , i = 1, · · · , N . 1: for episode t = 1, . . . , T do 2: . . . , N 5: for j = 1, . . . , n t do 6: Let all agents playx i,t 7: end for 9: for agent i = 1, . . . , N do 10: Since the agents cannot accurately estimate this continuous CDF F i,t (y) using finite samples, they instead construct the EDF where 1{·} is the indicator function. Then, using this EDF, the agents construct CVaR estimates of their cost functions J i (x t , ξ i ), denoted as CVaR αi [F i,t ], which they use to further construct zeroth-order estimates of their CVaR gradients asĝ where δ is the size of the perturbation on the action x i,t defined above. To ensure that the function values at the queried points during each time step are always feasible, we define the projection set Then, the agents perform the following projected gradientdescent update To analyze Algorithm 1, we utilize the smoothed approxima- where S −i = Π j =i S j , and B i , S i denote the unit ball and unit sphere in R di , respectively, and the size of the perturbation δ here serves as a smoothing parameter that controls how well C δ i (x) approximates C i (x). For details on zeroth-order optimization methods and their analysis, see (Nesterov & Spokoiny, 2017). The function C δ i (x) satisfies the following properties. The proof can be found in Appendix A.1. Lemma 2. Let Assumptions 1 and 2 hold. Then we have that From Lemma C.1 in (Bravo et al., 2018) , we have that where ∇ i denotes the partial derivative with respect to x i . However, as discussed before, it is not possible to accurately estimate the CVaR value C i (x t ) using finite samples of the cost function J i (x t , ξ i ). Instead, there will exist a CVaR estimation error, which we define aŝ which indicates that the CVaR gradient estimate is biased due to the use of finite samples. The analysis of the CVaR estimation errorε i,t plays a key role in the whole analysis of the regret of Algorithm 1. To bound the CVaR estimation error, we first present a lemma that bounds the difference between the CVaR values for two different CDFs. The proof of this lemma can be found in Appendix A.2. Lemma 3. Let F and G be two CDFs of two random variables and the random variables are bounded by U . Then we have that Lemma 3 states that the distance between two CVaR values is related to the distance between the corresponding CDFs. By substituting F = F i,t and G =F i,t into Lemma 3 and applying the Dvoretzky-Kiefer-Wolfowitz (DKW) inequality, we have that with probability at least 1 −γ. Combining inequality (6) with the sampling strategy defined in equation (1), the accumulated error of CVaR estimation can be bounded, which is given in the following lemma whose proof can be found in Appendix A.3.
Lemma 4. Given a confidence levelγ and the sampling strategy in equation (1), we have that the following inequality holds: The following result provides a generic regret decomposition of Algorithm 1. The proof can be found in Appendix A.4. Lemma 5. Let Assumptions 1 and 2 hold. Then, the regret of Algorithm 1 satisfies , Ω > 0 is a constant that represents the error from projection P, and B 1 as in (7).
Lemma 5 decomposes the regret into two terms, a zerothorder error term and a CVaR estimation error term. By selecting η and δ appropriately, we can show that Algorithm 1 is no-regret. In the following theorem,Õ hides constant factors and poly-logarithmic factors of T . In contrast, the standard notation O only hides constant factors. Theorem 1. Let Assumptions 1 and 2 hold and select . Suppose that n t is chosen as in equation (1) with a ∈ (0, 1), and the EDF and the gradient estimate are defined as in equations (2) and (3), respectively. Then, Algorithm 1 achieves regret Proof. Substituting δ, η and B 1 into the regret bound Err(ZO) + Err(CVaR) in Lemma 5, we ob- . The proof is complete.
As shown in Theorem 1, although it is impossible to obtain accurate CVaR values using finite bandit feedback, our method still achieves sub-linear regret with high probability. Notice that the choice of the risk level α i can also affect the regret. Specifically, a lower value for α i can result in higher regret, since it is harder to get samples under the α i tail of the distribution.

Improving the Algorithm Regret
In this section, we propose two variants of Algorithm 1 that improve the regret. The first variant reduces the accumulated error of the CVaR estimates by using samples from the previous iteration. The second variant employs residual feedback (Zhang et al., 2020a;b) to reduce the variance of the CVaR gradient estimates. A relevant analysis is given in the following two subsections, respectively.

Improving the CVaR Estimation Accuracy
The accuracy of the CVaR estimation in Algorithm 1 depends on the number of samples of the cost functions at each iteration according to equation (6); the more samples, the better the CVaR estimation accuracy. To further improve the CVaR estimation accuracy, we propose a modification to Algorithm 1 that reuses samples from the previous iteration, effectively increasing the number of available samples per iteration while maintaining the number of new samples the same. First, we make the following assumption on the variation of the cumulative distribution function.
Assumption 3 states that the variation of the CDF across two consecutive time steps is bounded by the distance between the corresponding unperturbed actions. It means that if x t is close to x t−1 , then the corresponding cost function values J i (x t , ξ i ) and J i (x t−1 , ξ i ) for every ξ i should also be close to each other, and so should be the two CDFs. Note that the bound in Assumption 3 is also related to the smoothing parameter δ, since the played action is in fact the perturbed one, i.e.,x t . Moreover, note that this bound cannot go to 0 by decreasing the smoothing parameter δ, which implies that the variation in the CDF should be dominated by the distance between x t and x t−1 .
The proposed risk-averse learning algorithm with sample reuse is illustrated in Algorithm 2 that can be found in Appendix B. Specifically, assuming that the agents can sample the cost functions n t times at every time step t, for t ≥ 2, we define a new EDF as where N t = n t + n t−1 . For t = 1, we set the initial value asF i,1 =F i,1 and N 1 = n 1 . Using this sampling strategy, we design the CVaR gradient estimate as Note that, as in Algorithm 1, this gradient estimate is biased since the estimation of CVaR uses not only finite samples, but also samples from the previous iteration. We denote the CVaR estimation error as Due to the use of previous samples, the analysis of the CVaR estimation error in this case becomes more complicated. The following lemma characterizes the CVaR estimation error and its the proof can be found in Appendix B.1.
Using the above bound on the CVaR estimation errorε i,t , we are able to show the following result. Proof. For ease of notation, we let δ = Σ 1 T − a 4 and Summing equation (11) over t, we obtain Adding the first term |ε i,1 | to both sides of this inequality, where Observe that the function f (T ) is monotonically decreasing in T and approaches negative infinity when T → ∞. Hence there exists T λ with f (T λ ) = −λ such that when T > T λ we have f (T ) < −λ, and thus This lemma shows that for the same confidence level 1 − γ, selecting δ = Σ 1 T − a 4 and η = Σ 2 T − 3a 4 in Algorithm 2 results in a bound on the accumulated CVaR estimation error that is strictly less than that achieved by Algorithm 1. The proof can be found in Appendix B.2. Similar to Lemma 5, we can decompose the regret into two sources of errors as shown below. Lemma 8. Let Assumptions 1 and 2 hold. Then, the regret of Algorithm 2 satisfies where Err(ZO) is the zeroth order error term as in Lemma 5.
Recall that the regret achieved by Algorithm 1 is bounded by In what follows, we show that the regret achieved by Algorithm 2 is strictly smaller than the regret bound achieved by Algorithm 1, i.e., Err(ZO) + Err(CVaR).

Proof.
Recall that Err(CVaR) = diDx δ B 1 . Adding and subtracting Err(CVaR) to the bound in Lemma 8, we have that Combining this inequality with Lemma 7, and assuming that T > T λ , we obtain that which completes the proof.
Theorem 2 shows that when Assumption 3 holds, the regret bound achieved by using previous samples is guaranteed to be smaller than that achieved without using prior information.
Note that hybrid sampling strategies are also possible that initially use samples only from the current iteration and eventually switch to using samples from the previous iteration too. Assuming that t 0 denotes the switching time after which previous samples are reused, the EDF is defined as Then, the regret achieved by this hybrid sampling strategy is analyzed below. The proof can be found in Appendix B.3. T − 3a 4 . Suppose that n t is chosen according to equation (1) with a ∈ (0, 1), and the EDF and the gradient estimate are defined as in equations (14) and (9), respectively. Then, there exists T λ(t0) > 0 such that when T > T λ(t0) , Algorithm 2 achieves regret R 2 Ci (T ) < Err(ZO) + Err(CVaR) and thus R 2

Reducing the CVaR Gradient Estimation Variance
Algorithm 2 discussed in Section 4.1 reduces the CVaR estimation error by using samples from the previous iteration.
In this section, we propose an alternative variation of Algorithm 1 that uses residual feedback (Zhang et al., 2020a;b) to reduce the variance of the zeroth-order CVaR gradient estimates. The risk-averse learning algorithm with residual feedback is illustrated in Algorithm 3 and can be found in Appendix C. Specifically, in Algorithm 3, the EDF is computed the same way as in Algorithm 1, but the gradient estimate now takes the form The CVaR gradient estimation is still biased and we can define the errorε Recall the definition ofε i,t in equation (10). Substituting in the expression forε i,t , we have that Taking the expectation of the gradient in equation (15) with respect to u i,t , we have that where the last equality is due to the fact that u i,t is independent ofF i,t−1 . Recall that the gradient estimate in Therefore, the expectation of the CVaR gradient estimate using residual feedback is the same as that in Algorithm 1. The following result analyzes the regret achieved by Algorithm 3. The proof can be found in Appendix C. T − a 4 . Suppose that n t is chosen according to equation (1) with a ∈ (0, 1), and the EDF and the gradient estimate are defined as in equations (2) and (15), respectively. Then, when T ≥ (8N 2 3 ) 1 a , Algorithm 3 achieves the regret R 3 Ci (T ) =Õ(T 1− a 4 ) with probability at least 1 − γ.
More precisely, Algorithm 3 actually achieves the regret R 3 ; see Appendix C.2 for more details. Note that the poly-logarithmic term ln(T ) in the regret bound achieved by Algorithm 3 is dominated by the polynomial term T 1− a 4 when T is large. Recall also that Algorithm 1 achieves regret R 1 . Ignoring the logarithmic dependence in the regret for large T , we obtain that the regret bound achieved by Algorithm 3 is strictly less than that achieved by Algorithm 1 when U > D x d i L 0 N 3 2 α i S 2 (α).

Numerical Experiments
Consider a Cournot game involving two risk-averse firms (agents) in the same market with different risk levels α i . We let α 0 = 0.5 and α 1 = 0.3, i.e, firm 1 is more risk sensitive than firm 0. Suppose that firm i supplies the market with a quantity x i , and the total supply of both firms defines the price of the goods in the market. We assume that the cost function for each firm i ∈ {0, 1} is defined as

Risk-Averse No-Regret Learning in Online Convex Games
is a uniform random variable. The cost term ξ i x i models the uncertainty in the market, which is proportional to production. The goal of each firm is to minimize the CVaR of their local cost function.
Recall the definition of the regret in Section 2, and note that it is not possible to compare the performance of Algorithm 1, 2 and 3 in terms of regret, since the baseline term minx i∈Xi and there is no golden rule to help select this sequence. In addition, computing the analytical solution to the baseline term is challenging due to the variational definition of CVaR. Instead, in what follows, we compare Algorithms 1,2 and 3 in terms of their empirical performances. Specifically, we run Algorithms 1, 2, and 3 and calculate the CVaR values achieved for each action. The algorithm with lower CVaR values is preferred since it achieves better performance in terms of risk-aversion.
The number of samples used by Algorithm 1 is determined by equation (1) and is shown in Figure 1. We implement a hybrid sampling strategy for Algorithm 2 and select the switching time step as 15000, after which prior samples are reused as in equation (14). The reason for this choice is that after 15000 time steps the number of samples becomes small (less than or equal to 3), which causes large errors in CVaR estimation. All other parameters in Algorithms 1, 2 and 3 are tuned so that the three algorithms achieve individually their best performance. Figure 2 compares empirically the performance of Algorithms 1 and 2. We observe that both Algorithms 1 and 2 both converge to the same CVaR values, but Algorithm 2 that reuses samples converges at a faster speed. Indeed, the learning rates of both algorithms depend on the number of samples; Algorithm 2 converges faster because sample reuse increases the effective number of samples per iteration and, as a result, decreases the CVaR estimation errors. This allows for a larger learning rate. Figure 3 shows the variance reduction effect achieved by Algorithm 3 that employs residual feedback to estimate the CVaR gradients. Note the very low variance (almost non-existent) associated with the blue and orange curves. As with Algorithm 2, residual feedback allows Algorithm 3 to use a larger learning rate and still converge to the same CVaR values as Algorithm 1. Additional numerical simulations for different sampling strategies are provided in Appendix D, where we also discuss convergence to the Nash equilibrium in practice.
Motivated by the improvements in performance that can be achieved by reusing prior samples to estimate the CVaR values (Algorithm 2) and relying on residual feedback to estimate the CVaR gradients (Algorithm 3), it is of interest to analyze the combined effect of these methods for risk-averse learning in online convex games. However, the theoretical analysis of this method is nontrivial and, for this reason, it is left for future research.

Conclusion
In this work, we proposed a first no-regret algorithm for riskaverse online convex games. Our algorithm relied on a new sampling strategy to estimate the CVaR values of the agents' cost functions, and a zeroth-order estimator of the CVaR gradients to update the agents' actions. To further improve the regret bounds achieved by our algorithm, we proposed two novel modifications; one that reuses samples from the previous iteration to better estimate the CVaR values and another that uses residual feedback to reduce the variance of the CVaR gradient estimation. We illustrated our proposed method on an online market example modeled as a Cournot game.
Tamkin, A., Keramati, R., Dann, C., and Brunskill, E. Distributionally-aware exploration for cvar bandits. In for any p 1 , p 2 ∈ X δ i and θ ∈ [0, 1], . Here we denote Ew i∼Bi,u−i∼S−i as E due to space limit. Thus we have which completes the proof.

According to the definition of
where the last inequality is due to the fact that w i ≤ 1, u i ≤ 1.

A.2 Proof of Lemma 3
Before the proof of Lemma 3, we first give the following result.
Lemma 9. Let F be the CDF of a non-negative random variable bounded by U , then we have that

Proof. It follows that
Since a = a 0 dy = ∞ 0 1{y ≤ a}dy, we obtain that This ends the proof.
Now we are ready to give the proof of Lemma 3.

Proof. According to the CVaR property, we have
Since ν F is the value that minimizes the CVaR α [F ], we further obtain that Using Lemma 9, we can obtain By symmetry, we can bound CVaR α [G] − CVaR α [F ] as well and the proof is omitted. The proof is complete.

A.3 Proof of Lemma 4
We first give the DKW inequality, which is helpful in our subsequent analysis.
Lemma 10 (DKW inequality). Let F be the CDF of a random variable andF be the empirical CDF obtained by n i.i.d. samples. For a gien constant > 0, we have Now we are ready to show the proof of Lemma 4.

Proof.
According to the DKW inequality, we have that Define the events in (18) as A t . Recall that γ =γT , then the following holds with probability at least 1 − γ due to the fact that 1 − P{ Combining with the sampling strategy defined in equation (1), and applying Lemma 3, the accumulated error of CVaR estimation can be bounded as follows where the last inequality holds due to the fact that 1 1− a 2 < 2, which completes the proof.

A.4 Proof of Lemma 5
Proof. We first present an observation.
Observation 1: There exist a constant Ω > 0 such that is L 0 -Lipschitz continuous, we can easily obtain the claim.
We have that Since where the last inequality follows from equation (20).

3:
Each agent samples u i,t ∈ S di , i = 1, . . . , N 4: Each agent playx i,t = x i,t + δu i,t , i = 1, . . . , N 5: for j = 1, . . . , n t do 6: Let all agents playx i,t 7: end for 15: end for Applying Observation 1 and (22) into the inequality above, it gives that where the last inequality follows from the fact that |Ĉ i | ≤ U and ĝ i, Proof. In order to give the formal proof, we need to introduce some new definitions. Define a new random variablě

B. Proofs of Key Results
, z t is an independent Bernoulli random variable with P{z t = 1} = nt Nt . Define the events B t := {#(z t = 1) = n t from N t samples ofJ i,t }, where # denotes the times that the event occurs. Then we define the conditional expectation ofJ i,t given event B t asJ i,t = E[J i,t |B t ], which is still a random variable (Durrett, 2019). Define the CDF ofJ i,t asF i,t , then we have that where the last equality is obtained by definitions of the random variables z t , J i,t , J i,t−1 . The second last equality is due to the fact that B t is only related to z t , and z t is independent of J i,t ,J i,t−1 . Then it gives that where the last inequality is due to n t−1 ≤ n t and thus nt−1 Nt ≤ 1 2 . From the definition ofJ i,t , we have thatF i,t is an EDF of F i,t . Applying DKW inequality, we have that, for t ≥ 2 Define the event in (26) as E t . Then the following holds with the probability at least 1 − γ due to the fact that 1 − P{ Together with Assumption 3, the following holds with probability at least 1 − γ for ∀t = 2, . . . , T . Then, applying Lemma 3, it gives that where the inequality holds due to the fact that The proof is complete.
Note that β = 4d 2 i L 2 0 N η 2 δ 2 . Telescoping this inequality and rearranging the term, we have that The proof ends by using ḡ i,t ≤ ḡ t .

C.2 Proof of Theorem 3
Proof. With the result in (16) and following similar lines as in the proof of Lemma 5, it can be verified that the following holds whereε i,t as defined in (10). Applying Lemmas 4 and 11 and substituting the bounds into the inequality above, it gives that T − a 4 , we have β = 4d 2 i L 2 0 N η 2 δ 2 = 4N 2 3 T −a ≤ 1 2 when T ≥ (8N 2 3 ) 1 a . Therefore, we have 1 1−β ≤ 2, and it follows that Substituting δ and η into this inequality and we can get R 3 Ci (T ) = O(D x d i L 0 N S(α) ln(T /γ)T 1− a 4 ). The proof is complete.

D. Additional Numerical Experiments
We provide additional simulation results for different sampling strategies related to different confidence levels γ. Two different sampling strategies are shown in Figure 4. Figure 5 shows that Algorithm 1 converges faster if more samples are collected and large sample size can decrease the variance of the algorithm. Moreover, since risk-neural learning is a special case of risk-averse learning by selecting α i = 1, i = 1, . . . , N , our risk-averse learning algorithms can be also used for risk-neutral games. Although in risk-averse games it is typically hard to calculate the Nash equilibrium, in risk-neutral games calculating the Nash equilibrium is possible. We define the expected cost function of agent i as u i = E ξi [J i ] = E ξi [−(2 − j x j )x i + 0.1x i + ξ i x i + 1] = −(2 − j x j )x i + 0.6x i + 1, where ξ i ∼ U (0, 1). With this expected cost function, this risk-neural game becomes a convex and monotone game. For this class of games, (Rosen, 1965) has shown that a unique Nash equilibrium exists. Specifically, setting the gradients of the expected cost function equal to 0, we can calculate the Nash equilibrium as (0.467, 0.467). Figure 6 shows that our algorithm converges to a neighborhood of the Nash equilibrium. This experiment verifies the correctness of our methodology.