How would one implement a multi-agent environment with asynchronous action and rewards per agent?

Question

In a single agent environment, the agent takes an action, then observes the next state and reward:

for ep in num_episodes:
    action = dqn.select_action(state)
    next_state, reward = env.step(action)

Implicitly, the for moving the simulation (env) forward is embedded inside the env.step() function.

Now in the multiagent scenario, agent 1 ($a_1$) has to make a decision at time $t_{1a}$, which will finish at time $t_{2a}$, and agent 2 ($a_2$) makes a decision at time $t_{1b} < t_{1a}$ which is finished at $t_{2b} > t_{2a}$.

If both of their actions would start and finish at the same time, then it could easily be implemented as:

for ep in num_episodes:
    action1, action2 = dqn.select_action([state1, state2])
    next_state_1, reward_1, next_state_2, reward_2 = env.step([action1, action2])

because the env can execute both in parallel, wait till they are done, and then return the next states and rewards. But in the scenario that I described previously, it is not clear how to implement this (at least to me). Here, we need to explicitly track time, a check at any timepoint to see if an agent needs to make a decision, Just to be concrete:

for ep in num_episodes:
    for t in total_time:
       action1 = dqn.select_action(state1)
       env.step(action1) # this step might take 5t to complete. 
       as such, the step() function won't return the reward till 5 t later. 
        #In the mean time, agent 2 comes and has to make a decision. its reward and next step won't be observed till 10 t later. 

To summarize, how would one implement a multiagent environment with asynchronous action/rewards per agents?

Answer 1

The cleanest solution from a theoretical point of view is to switch over to a hierarchical framework, some framework that supports temporal abstraction. My favourite one is the options framework as formalised by Sutton, Precup and Singh.

The basic idea is that the things that you consider "actions" for your agents become "options", which are "large actions" that may take more than a single primitive time step. When an agent selects an option, it will go on "auto-pilot" and keep selecting primitive actions at the more primitive, fine-grained timescale as dictated by the last selected option, until that option has actually finished executing. In your case, you could:

• implement the first "primitive action" of an option to immediately apply all effects to the state, and append a sequence of "no-op" actions afterwards to make sure the option actually has a longer duration than a single primitive timestep, OR
• implement the very last primitive action of an option to actually apply changes to the state, and prepend a sequence of "no-op" actions in front of it to make the option take more time, OR
• something in between (i.e. actually make partial changes to the state visible during the execution of the option).

Since all legal choices for agents in your scenario appear to be options, i.e. you do not allow agents to select primitive actions at the more fine-grained timescale, you would only have to implement "inter-option" learning in your RL algorithms; there would be no need for "intra-option" learning.

In practice, if you only have a small number of agents and have options that take relatively large amounts of time, you don't have to actually loop through all primitive time-steps. You could, for example, compute the primitive timestamps at which "events" should be executed in advance, and insert these events to be processed into an event-handling queue based on these timestamps. Then you can always just skip through to the next timestamp at which an event needs handling. With "events" I basically mean all timesteps at which something should happen, e.g. timesteps where an option ends and a new option should be selected by one or more agents. Inter-option Reinforcement Learning techniques are basically oblivious to the existence of a more fine-grained timescale, and they only need to operate at precisely these decision points where one option ends and another begins.