# Unexpected results when comparing a greedy policy to a DQN policy

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

• @NeilSlater No, in fact, if I had access to the MDP's transitons probabilities, I would have also compared to an optimal policy (generated using policy iteration for example) and see if it corresponds to the greedy policy or not. Regarding the total number of servers, I don't think it has a direct impact on the quality of the decisions. Since the decisions are mostly related to the server class, the number of servers belonging to each class is used instead. – user5093249 Mar 4 '20 at 14:20
• If the total number of servers fluctuates, the rules/distribution of those fluctuations needs to be consistent, and not based on anything other than existing state or pure randomness. If there is signifcant hidden state (e.g. a monitoring process is spinning stuff up or down based on some metric you are not using), then a MDP model could be inaccurate enough that the best you could do is greedy. Other than that, the distribution of incoming tasks also has a large impact - the example in Sutton & Barto has one task with random priority arriving at each time step, do you have similar? – Neil Slater Mar 4 '20 at 15:58
• Regarding the distribution of task types, I used the uniform random distribution. I also used different distributions where a given task type has a higher probability than the others, but the results remain consistent, i.e. the learnt policy is the almost the same as the greedy one. – user5093249 Mar 4 '20 at 16:38
• The reward is $-n$. In my example, the time taken by the smallest task to complete on the fastest server is $0.166 s$, and the heaviest task takes $2.5s$ to complete on the slowest server. The MDP time step is $0.1s$. – user5093249 Mar 4 '20 at 16:42
• I edited the question to include all completion times. – user5093249 Mar 4 '20 at 17:04

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

• Many thanks, very useful hints! I haven’t thought about the hidden state issue. You’re also right regarding the “exploit”. I should take that into account. Regarding your suggestion to expand the state to all servers, I was trying to avoid this from the beginning, as I have a large number of unique servers: around 2500 for the training dataset and around 800 for the test dataset. I thought it may not be efficient to provide such a higher number of inputs to the DQN. I thought a state representation with the number of servers of each class would be much more compact. – user5093249 Mar 5 '20 at 10:14
• @user5093249 You don't have to identify unique servers, just how many of each server are in the new states. I.e. instead of having state of how many free servers by type there are, expand to cover how many are free now, how many are 0.1s from being free, how many are 0.2s from being free etc. In that case when an agent assigns a heavy task the state will change differently to when it assigns a light task, and this is the main improvement you need IMO – Neil Slater Mar 5 '20 at 10:19
• I see, I misunderstood at the beginning. Then, this is better indeed. Thanks! – user5093249 Mar 5 '20 at 10:23
• following up on your answer, it turned out the change in the state representation did not have any impact. The DQN still ends up behaving greedily. Also, to rule out the effects of 2., 3. and the secondary effect you mentioned, I performed a test with a fixed server set (with 6 servers of each type) and the behavior was the same. – user5093249 Mar 7 '20 at 17:20
• @user5093249: OK, without running the experiment myself I cannot say why you got that result. It is possible that greedy behaviour is optimal for your values (number of servers, specific times and distribution of task sizes). If you find a counter-example of a mesurably better policy, then you would know that it is not. DQNs are tricky to setup and train, so it's not possible at this "distance" from your experiment to rule out a problem with implementation. – Neil Slater Mar 7 '20 at 18:17