Answers.Body: <p>You could take a look into <a href="https://ai.stackexchange.com/a/13255/2444">options</a>, (discrete-time) semi-MDPs, and multi-agent RL.</p>
  <p>An option is a generalisation of an action. Mathematically, it's defined as a tuple <span class="math-container">$\langle\mathcal{I}, \pi, \beta\rangle$</span> composed of</p>
  <ul>
  <li>an initiation set <span class="math-container">$\mathcal{I} \subseteq \mathcal{S}$</span>,</li>
  <li>a policy <span class="math-container">$\pi: \mathcal{S} \times \mathcal{A} \rightarrow [0, 1]$</span>, which gives the probability of taking a certain action in a certain state, and</li>
  <li>a termination condition <span class="math-container">$\beta: \mathcal{S}^+ \rightarrow [0, 1]$</span>, which gives the probability of terminating in a certain state.</li>
  </ul>
  <p>The policy is the function that you use to behave from a state in the initiation set until a termination condition is met.</p>
  <p>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.</p>
  <p>The framework of options was initially introduced in a single-agent setting <a href="https://www.sciencedirect.com/science/article/pii/S0004370299000521" rel="nofollow noreferrer">here</a>. However, I found a few papers that extend it to the multi-agent setting</p>
  <ul>
  <li><a href="https://dl.acm.org/doi/abs/10.1145/375735.376302" rel="nofollow noreferrer">Hierarchical Multi-Agent Reinforcement Learning</a> (2001, AAMAS)</li>
  <li><a href="https://www.aaai.org/ocs/index.php/FLAIRS/FLAIRS15/paper/viewFile/10420/10357" rel="nofollow noreferrer">Using Multi-Agent Options to Reduce Learning Time in Reinforcement Learning</a> (2015, AAAI)</li>
  <li><a href="https://arxiv.org/pdf/1910.09508.pdf" rel="nofollow noreferrer">Multi-agent Hierarchical Reinforcement Learning with Dynamic Termination</a> (2019, pre-print)</li>
  </ul>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-04-27T10:03:28.343Z
Answers.LastActivityDate: 2022-04-27T10:03:28.343Z
Answers.UserDisplayName: nbro
Answers.Body: <p>&quot; ... 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.<br />
  ... where vehicles on a 2-lane road can perform lane changing actions&quot;:</p>
  <ul>
  <li><p>&quot;Reinforcement Learning Baselines (from OpenAI) applied to Autonomous Driving</p>
  <p>This Research is aiming to address RL approaches to solve Urban driving scenarios such as (but not limited ): Roundabout, Merging, Urban/Street navigation, <strong>Two way navigation</strong> (pass over the opposite direction lane), self parking, etc...&quot;.</p>
  </li>
  <li><p>GitHub - <a href="https://github.com/pinakigupta/BehaviorRL" rel="nofollow noreferrer">Reinforcement Learning based Autonomous Driving (AD)</a></p>
  </li>
  </ul>
  <p> </p>
  <ul>
  <li>&quot;Simulation of Urban MObility&quot; (SUMO) is an open source, highly portable, microscopic traffic simulation package designed to handle large road networks and different modes of transport.
  <ul>
  <li>Paper - <a href="https://www.researchgate.net/publication/354696888_Using_Deep_Reinforcement_Learning_to_Coordinate_Multi-Modal_Journey_Planning_with_Limited_Transportation_Capacity" rel="nofollow noreferrer">Using Deep Reinforcement Learning to Coordinate Multi-Modal Journey Planning with Limited Transportation Capacity</a> - September 2021 - Conference: SUMO User Conference 2021, At: Virtual - Berlin, Germany</li>
  <li>GitHub - <a href="https://github.com/eclipse/sumo/tree/v1_5_0" rel="nofollow noreferrer">Simulation of Urban MObility</a></li>
  <li>GitHub - <a href="https://github.com/lcodeca/rllibsumoutils" rel="nofollow noreferrer">RLlib+SUMO Utils</a><br />
  Python3 library able to connect the RLlib framework with the SUMO simulator.</li>
  </ul>
  </li>
  </ul>
  <p> </p>
  <ul>
  <li><p><a href="https://hal.archives-ouvertes.fr/hal-03613558" rel="nofollow noreferrer">A Methodology to Build Decision Analysis Tools
  Applied to Distributed Reinforcement Learning</a> - Cedric Prigent, Loıc Cudennec, Alexandru Costan, Gabriel Antoniu - Submitted on 18 Mar 2022<br />
  ... In this context, a significant effort is made by researchers to find an efficient trade-off between the accuracy of the results, the <strong>computing time</strong> and the energy consumption.&quot;.</p>
  </li>
  <li><p><a href="https://proceedings.mlr.press/v139/domingues21a.html" rel="nofollow noreferrer">Kernel-Based Reinforcement Learning: A Finite-Time Analysis</a> - 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.<br />
  <strong>Abstract</strong> - 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.&quot;.</p>
  </li>
  </ul>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-27T20:28:31.517Z
Answers.LastActivityDate: 2022-05-27T20:28:31.517Z
Answers.UserDisplayName: Rob
Body: <p>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).</p>
  <p>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.</p>
  <p>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?</p>
  <p>I would greatly appreciate if anyone could point me in the right direction on bypassing this mental block, it is driving me crazy.</p>
  
Tags: <reinforcement-learning><reference-request><proximal-policy-optimization><semi-mdp><multi-agent-rl>
Title: How to model a multi-agent reinforcement learning problem where actions of different agents can take different durations?
UserDisplayName: hridayns
ThreadText: # How to model a multi-agent reinforcement learning problem where actions of different agents can take different durations?
  
  (Asked by: username_0 on 2022-04-24)
  
  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.
  
  **Tags:** reinforcement-learning, reference-request, proximal-policy-optimization, semi-mdp, multi-agent-rl
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2022-04-27. Score: 2
  
  You could take a look into [options](https://ai.stackexchange.com/a/13255/2444), (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](https://www.sciencedirect.com/science/article/pii/S0004370299000521). However, I found a few papers that extend it to the multi-agent setting
  
  * [Hierarchical Multi-Agent Reinforcement Learning](https://dl.acm.org/doi/abs/10.1145/375735.376302) (2001, AAMAS)
  * [Using Multi-Agent Options to Reduce Learning Time in Reinforcement Learning](https://www.aaai.org/ocs/index.php/FLAIRS/FLAIRS15/paper/viewFile/10420/10357) (2015, AAAI)
  * [Multi-agent Hierarchical Reinforcement Learning with Dynamic Termination](https://arxiv.org/pdf/1910.09508.pdf) (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 by username_2 on 2022-05-27. Score: 0
  
  " ... 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)](https://github.com/pinakigupta/BehaviorRL)
  
  * "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](https://www.researchgate.net/publication/354696888_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](https://github.com/eclipse/sumo/tree/v1_5_0)
    + GitHub - [RLlib+SUMO Utils](https://github.com/lcodeca/rllibsumoutils)  
      Python3 library able to connect the RLlib framework with the SUMO simulator.
  
  * [A Methodology to Build Decision Analysis Tools
    Applied to Distributed Reinforcement Learning](https://hal.archives-ouvertes.fr/hal-03613558) - 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](https://proceedings.mlr.press/v139/domingues21a.html) - 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.".
  
  
  ---
  
  