How to model a multi-agent reinforcement learning problem where actions of different agents can take different durations?

Question

I am confused on a conceptual scale how I would be able to model a multi-agent reinforcement learning problem when each agent performing an action would take different durations to complete the action. This means that a certain action is performed over multiple steps and the learning sample would have that action attached to it (with different observations and rewards, possibly).

An example of this situation would be where vehicles on a 2-lane road can perform lane changing actions, but each of these actions may take anywhere between 2 - 5 seconds (or learning steps) to complete.

So, what action would need to be passed at every step? I am using RLlib framework. Is it even possible to do this? Or do all these agents have to have the same action duration / step length for any RL algorithm to work?

I would greatly appreciate if anyone could point me in the right direction on bypassing this mental block, it is driving me crazy.

Answer 1

You could take a look into options, (discrete-time) semi-MDPs, and multi-agent RL.

An option is a generalisation of an action. Mathematically, it's defined as a tuple $\langle\mathcal{I}, \pi, \beta\rangle$ composed of

• an initiation set $\mathcal{I} \subseteq \mathcal{S}$,
• a policy $\pi: \mathcal{S} \times \mathcal{A} \rightarrow [0, 1]$, which gives the probability of taking a certain action in a certain state, and
• a termination condition $\beta: \mathcal{S}^+ \rightarrow [0, 1]$, which gives the probability of terminating in a certain state.

The policy is the function that you use to behave from a state in the initiation set until a termination condition is met.

A semi-MDP is a special MDP where actions can take a variable amount of time. So, a set of options induces a semi-MDP.

The framework of options was initially introduced in a single-agent setting here. However, I found a few papers that extend it to the multi-agent setting

• Hierarchical Multi-Agent Reinforcement Learning (2001, AAMAS)
• Using Multi-Agent Options to Reduce Learning Time in Reinforcement Learning (2015, AAAI)
• Multi-agent Hierarchical Reinforcement Learning with Dynamic Termination (2019, pre-print)

I've only quickly skimmed through them, so I don't know if the approaches proposed in these papers are suitable for your case (and this also depends on whether your agents are cooperative, adversarial, etc.), and I also don't know if they have any free/available implementation on the web, but I think the information in this answer should put you in the right direction.

Answer 2

" ... how I would be able to model a multi-agent reinforcement learning problem when each agent performing an action would take different durations to complete the action.
... where vehicles on a 2-lane road can perform lane changing actions":

• "Reinforcement Learning Baselines (from OpenAI) applied to Autonomous Driving

  This Research is aiming to address RL approaches to solve Urban driving scenarios such as (but not limited ): Roundabout, Merging, Urban/Street navigation, Two way navigation (pass over the opposite direction lane), self parking, etc...".

• GitHub - Reinforcement Learning based Autonomous Driving (AD)

 

• "Simulation of Urban MObility" (SUMO) is an open source, highly portable, microscopic traffic simulation package designed to handle large road networks and different modes of transport.
  • Paper - Using Deep Reinforcement Learning to Coordinate Multi-Modal Journey Planning with Limited Transportation Capacity - September 2021 - Conference: SUMO User Conference 2021, At: Virtual - Berlin, Germany
  • GitHub - Simulation of Urban MObility
  • GitHub - RLlib+SUMO Utils
    Python3 library able to connect the RLlib framework with the SUMO simulator.

 

• A Methodology to Build Decision Analysis Tools Applied to Distributed Reinforcement Learning - Cedric Prigent, Loıc Cudennec, Alexandru Costan, Gabriel Antoniu - Submitted on 18 Mar 2022
  ... In this context, a significant effort is made by researchers to find an efficient trade-off between the accuracy of the results, the computing time and the energy consumption.".

• Kernel-Based Reinforcement Learning: A Finite-Time Analysis - Omar Darwiche Domingues, Pierre Menard, Matteo Pirotta, Emilie Kaufmann, Michal Valko - Proceedings of the 38th International Conference on Machine Learning, PMLR 139:2783-2792, 2021.
  Abstract - We consider the exploration-exploitation dilemma in finite-horizon reinforcement learning problems whose state-action space is endowed with a metric. We introduce Kernel-UCBVI, a model-based optimistic algorithm that leverages the smoothness of the MDP and a non-parametric kernel estimator of the rewards and transitions to efficiently balance exploration and exploitation.".