Unexpected results when comparing a greedy policy to a DQN policy

Question

I am trying to work on a variation of the Access-Control Queuing Task problem presented in Chapter 10 of Sutton’s reinforcement learning book [1].

Specific details of my setup are as follows:

• I have different types of tasks that arrive to a system (heavy/moderate/light with heavy tasks requiring more time to be processed.). The specific task type is chosen uniformly at random. The task inter-arrival time is $0.1s$ on average.
• I have different classes of servers that can process these tasks (low-capacity; medium capacity; high capacity; with high capacity servers having a faster processing time). When I select a specific server from a given class, it becomes unavailable during the processing time of the task assigned to it. Note that the set of servers (and as a result the number of servers of each class) is not fixed, it instead changes periodically, according to the dataset used to model the set of servers (so specific servers may disappear and new ones may appear, as opposed to the unavailability caused by the assignment). The maximum number of servers of each class is $10$.
• My goal is to decide which class of server should process a given task, in a way that minimizes the sum of the processing times over all tasks.

The specific reinforcement learning formulation is as follows:

• State: the type of task (heavy/moderate/light) ; the number of available low capacity servers; the number of available medium capacity servers; the number of available high capacity servers
• Actions: (1) Assign the task to a low capacity server (2) assign the task to a medium capacity server (3) assign the task to a high capacity server (4) a dummy action that has a worse processing time than the servers with low capacity. It is selected when there are no free servers.
• Rewards: the opposite of the processing time, where the processing times are as follows (in seconds):

|               | Slow server | Medium Server | Fast server | "Dummy action" |
|---------------|-------------|---------------|-------------|----------------|
| Light task    | 0.5         | 0.25          | 0.166       | 0.625          |
| Moderate task | 1.5         | 0.75          | 0.5         | 1.875          |
| Heavy task    | 2.5         | 1.25          | 0.833       | 3.125          |

My intuition for formulating the problem as an RL problem is that 'Even though assigning Light tasks to High capacity servers (i.e. being greedy) might lead to a high reward in the short term, it may reduce the number of High capacity servers available when a Heavy task arrives. As a result, Heavy tasks will have to be processed by lower capacity servers which will reduce the accumulated rewards'.

However, when I implemented this (using a deep Q-network[2] specifically), and compared it to the greedy policy, I found that both approaches obtain the same rewards. In fact, the deep Q-network ends up learning the greedy policy.

I am wondering why such a behaviour occured, especially that I expected the DQN approach to learn a better policy than the greedy one. Could this be related to my RL problem formulation? Or there is no need for RL to address this problem?

[1]Sutton, R. S., & Barto, A. G. (1998). Introduction to reinforcement learning (Vol. 135). Cambridge: MIT press.

[2]Mnih, V., Kavukcuoglu, K., Silver, D., Rusu, A. A., Veness, J., Bellemare, M. G., ... & Petersen, S. (2015). Human-level control through deep reinforcement learning. Nature, 518(7540), 529-533.f

Answer 1

Your problems appear to derive from a non-Markov state description. In brief, the agent has no way to ever learn that "heavy jobs will make a server unavailable for longer" and this is further compounded by arbitrary state transitions every 10 steps whilst the agent cannot track time.

Looking at the example from Sutton & Barto, you should note that they took care to model a valid MDP. Servers become available at random on each time step, and there is no hidden state. In your case you have three sources of hidden data that affects state evolution systematically. If an agent had some data about these then it might be able to use to optimise choices better:

1. Servers in use due to tasks assigned by the agent return deterministically n steps after the action that assigned them. The agents inability to track this is likely to be your largest problem - there is no data flow in RL that will allow the agent to associate the heavier jobs or slower servers with making a server unavailable for longer, so it never "sees" the clash of resource management that you want it to resolve.

2. Every 10 timesteps there is an arbitrary change to server availability. This is a problem because it is entirely predictable on which time steps it can occur, but the agent does not know the current timestep.

3. You are driving this from a dataset, not randomly, so the impact on this will vary depending on how the dataset evolves over time. A particularly bad case here would be if the dataset represented a "working day" so that there were clear timezones when availability followed different patterns. The agent has no data input in the state in order to associate patterns of use (such as the time of day), so the environment either becomes an online learning problem (agent must continuously learn and adapt to new patterns as they arise), or it must come up with a strategy that works in some average over all possible patterns.

In addition I can see a possible secondary effect, an "exploit" in the simulation, that may have a noticeable effect depending on how often specific servers drop out of the pool. It would appear if an agent assigns a task to a server, that you have no mechanism to unassign that task should the server drop out. So an aggressive agent that assigns greedily to the best available servers will get extra "free" time on the high capacity servers if it always claims them. As the agent doesn't know when the drop outs could happen, this effect competes with the average of leaving servers available just in case a heavy task arrives.

How to fix it? It depends on how much of your simulation is fixed by your requirements. You can either adjust the simulation to match your current state representation, or you can change the state representation to capture more system data from the simulation.

Probably the simplest state change would be to expand the list of servers to always include all servers, and for each unavailable server to have a "ticker" to show how many time steps before it becomes available. To make the problem smaller, you could maybe just track 1-10 ticks and have a combined state for (>10), as that will expose enough of the key state information that the agent can make decisions about pushing easy tasks into medium or low capacity servers. This does not need to be done to the level server id if the servers truly are interchangeable otherwise. So instead of an array of number of free servers by type, consider that it expands to a table with number of free servers by type at one end, then a column of number of servers by type with 0.1s remaining until they are free, then a column for servers that still have 0.2s remaining etc etc