Risk-Averse No-Regret Learning in Online Convex Games
Risk-Averse No-Regret Learning in Online Convex Games
复制标题
DOI：
10.48550/arxiv.2203.08957
复制
发表时间：
2022-03
期刊：
影响因子：
--
通讯作者：
Zifan Wang;Yi Shen;M. Zavlanos
中科院分区：
文献类型：
--
作者：
Zifan Wang;Yi Shen;M. Zavlanos
我们考虑一个具有规避风险代理的在线随机游戏，其目标是学习最佳决策，最大限度地降低产生高成本的风险。具体来说，我们使用条件风险价值（CVaR）作为风险度量，代理可以使用强盗反馈以仅其所选操作的成本值的形式进行估计。由于成本函数的分布取决于通常不可观察的所有智能体的行为，因此它们本身是未知的，因此成本的 CVaR 值很难计算。为了应对这一挑战，我们提出了一种新的在线风险规避学习算法，该算法依赖于使用通过适当采样成本函数来估计的 CVaR 值计算出的 CVaR 梯度的单点零阶估计。我们证明该算法以高概率实现次线性后悔。我们还提出了该算法的两种变体来提高性能。第一个变体依赖于新的采样策略，该策略使用先前迭代中的样本来提高 CVaR 值的估计精度。第二种变体采用残差反馈，该残差反馈使用来自先前迭代的 CVaR 值来减少 CVaR 梯度估计的方差。我们从理论上分析了这些变体的收敛特性，并说明了它们在我们建模为古诺博弈的在线市场问题上的表现。
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.