In Sutton and Barto's reinforcement learning book, in multi-armed bandit problem a phrase has been used. "finding an optimal action" using greedy/$\epsilon$-greedy algorithm. When it is said that an algorithm "finds the optimal action " ?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
In the bandit setting, to each arm is associated an unknown reward distribution. The optimization goal is to find a policy (a series of level pulls) which yields the maximum sum of rewards.
"Finding an optimal action" thus refers to the process of discovering the arm which gives you the most reward.
-
$\begingroup$ what is that process ? sampling is used to estimate the mean. so how to tell at which step I have found the optimal action ? $\endgroup$ Commented May 1, 2014 at 13:58
-
$\begingroup$ At which step: this is algorithm-specific. Some methods might provide some bounds, but in general I would say that you run you algorithm until it's "good enough". $\endgroup$ Commented May 6, 2014 at 21:08