5 votes

Does one player best responding to sample from a mixed strategy, and the other player minimizing regret converge to a Nash eq in a zero sum game?

No, it's not true. Consider this game where the row player's actions are A,B,C and column's are D,E (shown are the row player's payoffs): ...
  • 7,110
3 votes
Accepted

Rademacher complexity beyond the agnostic setting

(a) If you don't assume that you're "competing" against $f\in F$, you must make some assumption about the larger function class to which $f$ belongs -- otherwise, by standard no-free-lunch theorems, ...
  • 10.1k
3 votes
Accepted

Average Regret Bounds for Linear Stochastic Bandits

Using the "doubling trick," you can turn your favorite high probability algorithm (e.g. LinUCB) to be an anytime algorithm with expected regret as a function of $T$, usually giving a $\tilde{O}(\sqrt{...
  • 11.8k
2 votes
Accepted

Bayes-consistent cost-sensitive classification

I'm not sure if this is what you're looking for, but people have studied consistency of surrogate risk minimization. There, we define a surrogate loss function $L$ and a link $\psi$. We first minimize ...
  • 7,110
1 vote

Follow the Perturbed Leader for nonlinear cost functions

Here is what you are looking for. It is quite new: https://arxiv.org/pdf/1810.07362.pdf

Only top scored, non community-wiki answers of a minimum length are eligible