R-learning is an off-policy control method for the advanced version of the
reinforcement learning problem in which one neither discounts nor divides
experience into distinct episodes with finite returns. In this case one seeks
to obtain the maximum reward per time step. The
value functions for a policy, , are defined relative to the
average expected reward per time step under the policy, :
There are subtle distinctions that need to be drawn between different kinds of optimality in the undiscounted continuing case. Nevertheless, for most practical purposes it may be adequate simply to order policies according to their average reward per time step, in other words, according to their . For now let us consider all policies that attain the maximal value of to be optimal.
Other than its use of relative values, R-learning is a standard TD control method based on off-policy GPI, much like Q-learning. It maintains two policies, a behavior policy and an estimation policy, plus an action-value function and an estimated average reward. The behavior policy is used to generate experience; it might be the -greedy policy with respect to the action-value function. The estimation policy is the one involved in GPI. It is typically the greedy policy with respect to the action-value function. If is the estimation policy, then the action-value function, , is an approximation of and the average reward, , is an approximation of . The complete algorithm is given in Figure 6.16. There has been little experience with this method and it should be considered experimental.
Example 6.7: An Access-Control Queuing Task This is a decision task involving access control to a set of servers. Customers of four different priorities arrive at a single queue. If given access to a server, the customers pay a reward of 1, 2, 4, or 8, depending on their priority, with higher priority customers paying more. In each time step, the customer at the head of the queue is either accepted (assigned to one of the servers) or rejected (removed from the queue). In either case, on the next time step the next customer in the queue is considered. The queue never empties, and the proportion of (randomly distributed) high priority customers in the queue is . Of course a customer can be served only if there is a free server. Each busy server becomes free with probability on each time step. Although we have just described them for definiteness, let us assume the statistics of arrivals and departures are unknown. The task is to decide on each step whether to accept or reject the next customer, on the basis of his priority and the number of free servers, so as to maximize long-term reward without discounting. Figure 6.17 shows the solution found by R-learning for this task with , , and . The R-learning parameters were , , and . The initial action values and were zero.
Exercise 6.11 Design an on-policy method for undiscounted, continuing tasks.