I have implemented an epsilon-greedy Monte Carlo reinforcement learning agent like suggested in Sutton and Barto's RL book (page 101). As far as I understood epsilon-greedy agents so far, the evaluation has to stop at some point to exploit the gained knowledge.
I do not understand, how to stop the evaluation here, because the policy update is linked to epsilon. So just setting epsilon equal to zero at some point does not seem to make sense to me.
I do not understand, how to stop the evaluation here, because the policy update is linked to epsilon. So just setting epsilon equal to zero at some point does not seem to make sense to me.
If by evaluation you mean the act of exploring new paths, it does not need to stop by changing epsilon to 0 instantly. Instead, in order to facilitate the convergence of the algorithm, the epsilon can be progressively decreased until it reaches 0.
I do not think your question is meant to be related with monte carlo specifically, but if this was not what you wanted to know, please comment.
But would not a epsilon value of 0 lead to an unintended policy update?
No, a value of epsilon equal to 0 will make you always choose your action according to the policy. I think what is confusing is that the "update" they make to the policy on the last for, is not an update. It is a statement saying the probability of taking such action. What it means is the following:
For action $a$, the probability of taking $a$ in state $S_t$, when $\epsilon$ is 0 is:
What this means is that when epsilon is 0, the action taken will always be the greedy action.
Before answering how to stop the evaluation phase and begin exploitation of those results, one must first answer when to stop it whereby the balance the project stakeholder wants between quality and cost is found. You won't always find that in books discussing pure research, so your question is an excellent one.
The algorithm the authors are discussing on that page (101) is based on the policy improvement theorem on page 78, and the appearance of the endless loop in the algorithm in the pseudo-code line "Repeat forever (for each episode)" is obviously worse than useless in a data center if the loop is not terminated, unless it is multi-agent, exploiting multiple threads, processes, virtual hosts, hardware accelerators, cores, or hosts, and the improvements are accessed for exploitation independently or symbiotically using some scheme.
In a deployed robot, an endless loop often has a legitimate a use case. "Repeat until shutdown," might be appropriate in a production algorithm or hardware embodiment if the robot's goal is, "Keep the living room clean." One must always try to place this theory in context when taking pure research and considering the applied research that may stem from it.
In real product and service development environments, how the balance is struck between quality of action and cost of determining it depends upon the problem size, expectations of the user or business, and the architecture of the computational resources you have. Consider some of these factors in more detail.
In a single thread, single core, von Neumann architecture, as is sometimes the case in an embedded environment, evaluation and exploitation are time sliced. In such a case, evaluation should stop and exploitation should begin when the probability that further evaluation will produce an improved result drops below the cost of further evaluation, based on some estimation of return and cost. This is a function of the above factors, although not a linear one.
We have considered training an LSTM network to determine the function in the epoch domain (roughly related to the time domain), although it is low on our priority list.
In an embedded process, a function that approximates return on further evaluation cost can be constructed, based on statistics gathered up to that point in current learning or over a longer period of operations. The function should be fast and inexpensive. In each cycle within the evaluation phase, the function can be evaluated and compared against a configurable probability threshold. Its configuration value can be an educated guess based on the perception of the value of further path exploration.
In a simulation environment, when more computing resources for parallel processes, exploiting OS or hardware facilities for that, the time slicing is either opaque or nonexistent respectively. In those cases, continuous improvement may be unbounded because the state-action graph is not finite.
