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,185
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.2k
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.9k
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,185
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
- 167
Only top scored, non community-wiki answers of a minimum length are eligible