Differential Semi-gradient Sarsa for Control

A Queue Without a Final Step

The task is an ongoing accept-or-reject problem. Customers continually arrive at a single queue, and the controller repeatedly decides what to do with the customer at the front. There is no single customer whose outcome defines success. Instead, the objective is to achieve strong long-term average reward across the continuing sequence of decisions.

Reading the Queue State

At each decision point, the state contains two pieces of information: the number of free servers and the priority of the customer currently at the front of the queue. The available action is either accept or reject. Accepting can produce an immediate reward and uses a server. Rejecting produces no reward and moves attention to the next customer.

What the Table Stores

In the tabular version, the learner stores one differential action-value estimate for every combination of state and action. A table entry therefore corresponds to a particular number of free servers, a particular current-customer priority, and either accept or reject. The estimate represents the learned long-term average-reward value associated with that state-action pair.

Following One Sarsa Update

Differential semi-gradient Sarsa applies repeated experience from the queue to the stored action-value estimates. At a high level, the learner starts with a current state and action, carries out that action, observes the immediate reward and next state, selects the next action, and uses this experience to update the estimate associated with the current state-action pair. The process then continues from the next state and next action.

• Represent the current state using free-server information and the priority of the queue-head customer.
• Use the current state and action to obtain an experience from the queue.
• Record the immediate reward and the next state.
• Select the next action for the continuing decision process.
• Update the differential action-value estimate for the current state-action pair.
• Continue the same loop for later customers.

The word differential identifies the objective: long-term average reward without discounting future rewards. The method is therefore suited to this continuing queue rather than a task organized around a finite discounted return.

Experiment Settings and Results

After 2 million steps, the reported learned average reward was about 2.31. This is a long-run performance estimate for the continuing queue. It is not the reward received from one particular customer or one isolated accept-or-reject decision.

Mistakes About the Queue

• Treating the state as only the number of free servers.

  The decision state contains both server availability and customer priority.

  Fix: Represent the state as the pair of free-server information and queue-head customer priority.

• Treating rejection as an action that produces the same kind of immediate reward as acceptance.

  Rejection produces no reward, while acceptance can produce an immediate reward.

  Fix: Record zero immediate reward for rejection and then continue with the next customer.

• Assuming the task ends after one customer.

  The queue is continually supplied with customers and the controller continues making decisions.

  Fix: Evaluate the method through long-term average reward over the continuing sequence.

• Assuming one learned table entry represents similar states automatically.

  The tabular representation gives each state-action pair its own estimate and does not share information between different states.

  Fix: Check which specific state-action entries have actually been experienced.

• Interpreting the value 2.31 as one customer's reward.

  The reported value is a learned average reward for the continuing task.

  Fix: Interpret it as long-run performance across the ongoing decision process.

Check Your Understanding

Key Takeaways

1. The queueing problem is continuing: customers keep arriving and decisions do not revolve around a final episode.
2. The state combines the number of free servers with the priority of the customer at the queue head.
3. The actions are accept and reject; acceptance can produce an immediate reward and uses a server, while rejection produces zero reward and moves to the next customer.
4. A tabular differential action-value estimate stores a separate long-term average-reward estimate for every state-action pair.
5. Differential semi-gradient Sarsa repeatedly uses queue experience to update these estimates without discounting future rewards.
6. The reported learned average reward was about 2.31 after 2 million steps, but rarely experienced states can remain unreliable because their entries receive insufficient data.