  The connection between games and no-regret algorithms has been widely studied
in the literature. A fundamental result is that when all players play no-regret
strategies, this produces a sequence of actions whose time-average is a
coarse-correlated equilibrium of the game. However, much less is known about
equilibrium selection in the case that multiple equilibria exist.
  In this work, we study the convergence of no-regret bidding algorithms in
auctions. Besides being of theoretical interest, bidding dynamics in auctions
is an important question from a practical viewpoint as well. We study repeated
game between bidders in which a single item is sold at each time step and the
bidder's value is drawn from an unknown distribution. We show that if the
bidders use any mean-based learning rule then the bidders converge with high
probability to the truthful pure Nash Equilibrium in a second price auction, in
VCG auction in the multi-slot setting and to the Bayesian Nash equilibrium in a
first price auction. We note mean-based algorithms cover a wide variety of
known no-regret algorithms such as Exp3, UCB, $\epsilon$-Greedy etc. Also, we
analyze the convergence of the individual iterates produced by such learning
algorithms, as opposed to the time-average of the sequence. Our experiments
corroborate our theoretical findings and also find a similar convergence when
we use other strategies such as Deep Q-Learning.
