Skip to content
Last Dictionary
Plane
Reinforcement LearningMathematics & StatisticsMachine Learning

regret

nounAlso: cumulative regret, simple regret, no-regret learning

In plain wordsHow much worse a learner did than it could have done had it known the best choice from the start — the price of having to learn by trying.

  1. The difference between the cumulative rewardreward, n.: The score an AI system receives after an action, telling it how good the outcome was. Reinforcement learning trains the system to collect as much reward as possible over time. an algorithm obtains over T rounds and the reward it would have obtained by always playing the best fixed option — in hindsight for adversarial problems, in expectation for stochastic ones. Regret measures the cost of learning in banditsmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others., online learningonline learning, n.: Learning from data that arrive one piece at a time, updating the model after each new example instead of training once on a fixed collection, as a spam filter does while emails stream in. and reinforcement learningreinforcement learning, n.: A way of teaching a computer program by trial and error: it tries actions, earns points for good results and penalties for bad ones, and gradually learns which choices pay off over time.: an algorithm whose regret grows sublinearly in T is called no-regret, because its average performance approaches that of the best option. Classic results set the yardsticks: Lai and Robbins showed that regret in stochastic bandits must grow at least logarithmically in T, a rate that UCBupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance. and Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far. achieve, while adversarial bandits and online convex optimization admit bounds of order √T. Simple regret, the quality of the final choice, matters instead when only the end result counts. No-regret learning in games converges to equilibria, the basis of counterfactual regret minimizationcounterfactual regret minimization, n.: A method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making. in poker.

    Logarithmic regret means the bandit makes only a modest number of bad pulls even after a million rounds.

RT=T μ∗−E[∑t=1Trt],μ∗=max⁡kμkR_T = T\,\mu^{*} - \mathbb{E}\left[ \sum_{t=1}^{T} r_t \right], \qquad \mu^{*} = \max_{k} \mu_k

Origin

From decision theory, where Leonard Savage proposed the minimax-regret criterion for decisions under uncertainty (1951). Tze Leung Lai and Herbert Robbins's 1985 analysis made regret the standard yardstick for bandit algorithms, and learning theory extended it to online learning, games and reinforcement learning.

Related

See also
  • multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others.
  • upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.
  • Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far.
  • online learningonline learning, n.: Learning from data that arrive one piece at a time, updating the model after each new example instead of training once on a fixed collection, as a spam filter does while emails stream in.
  • exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one.
  • counterfactual regret minimizationcounterfactual regret minimization, n.: A method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making.

Sources

  1. Savage, L. J. (1951). The Theory of Statistical Decision. Journal of the American Statistical Association 46(253), 55–67.
  2. Lai, T. L. & Robbins, H. (1985). Asymptotically efficient adaptive allocation rules. Advances in Applied Mathematics 6(1), 4–22.

Mentioned in

exploration–exploitation trade-offexploration–exploitation trade-off, n.: The choice between trying something new that might turn out better and sticking with what already works — like picking a familiar restaurant versus testing a new one., multi-armed banditmulti-armed bandit, n.: A puzzle named after a gambler choosing between slot machines: you must keep picking among options whose payoffs are unknown, learning which is best while wasting as few tries as possible on the others., online learningonline learning, n.: Learning from data that arrive one piece at a time, updating the model after each new example instead of training once on a fixed collection, as a spam filter does while emails stream in., counterfactual regret minimizationcounterfactual regret minimization, n.: A method for working out near-unbeatable strategies in games with hidden information, like poker, by repeatedly playing against itself and shifting each decision toward the moves it most regrets not making., Nash equilibriumNash equilibrium, n.: A stable standoff in a game: each player's choice is already their best answer to what the others are doing, so nobody gains by changing course alone — though the result need not be good for anyone., Thompson samplingThompson sampling, n.: A way to choose among uncertain options by picking each one about as often as it is likely to be the best, based on everything learned so far., upper confidence boundupper confidence bound, n.: A rule for choosing among uncertain options that gives each one a bonus for how little is known about it, so promising but rarely tried options get a fair chance.