Bandit Learning in Concave N -Person Games
This paper examines the long-run behavior of learning with bandit feedback in non-cooperative concave games. The bandit framework accounts for extremely lowinformation environments where the agents may not even know they are playing a game; as such, the agents' most sensible choice in this setting would be to employ a no-regret learning algorithm. In general, this does not mean that the players' behavior stabilizes in the long run: no-regret learning may lead to cycles, even with perfect gradient information. However, if a standard monotonicity condition is satisfied, our analysis shows that no-regret learning based on mirror descent with bandit feedback converges to Nash equilibrium with probability 1. We also derive an upper bound for the convergence rate of the process that nearly matches the best attainable rate for single-agent bandit stochastic optimization.
This paper presents a learning algorithm for participants in a strongly monotone convex game, such that if all participants use this learning algorithm, they converge to the unique Nash equilibrium of this game at a rate of O(n^{-1/3}) (i.e. at round n, each player is within O(n^{-1/3}) of their Nash equilibrium strategy). This extends a long line of work of understanding what sorts of equilibria learning strategies can/will converge to when used to play games (e.g. if everyone uses a low-regret strategy, the time-averaged play converges to a coarse correlated equilibrium).   The learning algorithm they propose can be thought of as a modification of online mirror descent. The main technical difficulty here is that online mirror descent is a first-order method, requiring the gradient of the loss function at the queried points, but in this setting only zeroth-order feedback (the loss from performing some action) is provided. Moreover, unlike other settings where it is possible to approximate the gradient of some point by zeroth-order feedback of several points (even just two) in the neighborhood of this point, here each player only has control over their own action (and thus cannot guarantee they can query multiple closeby points in the overall action space).   The trick the authors use to overcome this difficulty is called "simultaneous perturbation stochastic approximation", which allows one to get an "estimate" of a gradient at a point via a single zeroth-order query. The main idea is if one would like to query the gradient at some point x in R^d, they instead choose a random direction z_i in the unit d-sphere, and evaluate the function at x + delta*z_i. It can then be shown that f(x+delta*z_i)*d*z_i/delta is an unbiased estimator of the gradient of f~ at x, where f~ is some smoothed approximation to f. If f and its gradients are Lipschitz continuous, f~ gets closer and closer to f as delta goes to 0 (at the cost of the variance of this estimator exploding). Choosing delta to be something like n^{-1/3} optimizes this bias-variance tradeoff and leads to a convergence rate of O(n^{-1/3}).   I think this is a strong result. Monotone concave games are a large class of interesting games, and a natural setting for this sort of question given their unique equilibrium structure. I really liked the application of the perturbation trick, which has appeared in the literature before, but which I had not seen and is applied nicely here. I have not checked the technical details in the supplemental material carefully, but the proof sketch makes sense to me.   From a game theory perspective, it would be nice to have some slightly broader characterization of learning algorithms such that, if all players are running some learning algorithm in this class, then they converge to the Nash equilibrium of this game (at some convergence rate). This is a good first step in this direction, showing that there is some simple learning algorithm all learners can run to converge to a Nash equilbirium, but for the purpose of understanding how equilibria are achieved, it is unlikely that all players are running exactly this variant of mirror descent. I think it would be a very strong result if you could somehow show that if they are all using any sort of learning algorithm with "low X regret" (for some type of X regret), this convergence follows (such guarantees exist for convergence to CCE in general repeated games).   The paper was written exceptionally clearly -- as someone who does not work closely with mirror descent, I really appreciated the detailed preliminaries in section 2 and 3. I recommend this paper for acceptance.