Answers.Body: <p>RL is not limited to MDPs, but standard textbooks will probably start with that because the most common RL algorithms (like Q-learning) assume an MDP. So, an MDP is just a way to <strong>model</strong> the environment. RL is the way you learn in that environment and RL is just a <strong>trial-and-error approach to learning</strong>, where you get feedback (reinforcement) for your actions, but you can also solve MDPs with dynamic programming (see policy iteration).</p>
  <p>You can model multi-agent systems with Markov Games (aka Stochastic Games), which are a simple generalisation of MDPs. See <a href="https://nbro.gitlab.io/blogging/2024/03/17/mdps-are-markov-games/" rel="nofollow noreferrer">my blog post</a>.</p>
  <p>There are also other models, like <strong>PO</strong>MDPs, which are a generalisation of MDPs for other scenarios, in this case, <strong>p</strong>artially <strong>o</strong>bservable environments, i.e. you don't know exactly the state you're in.</p>
  <p>So, you can model your problem in different ways. Some problems may be modelled with MDPs, but the states may not be really fully observable, it's just an approximation. Sometimes it works. Take a look at the original DQN paper, where they tried to approximate states with a sequence of images.</p>
  <p>Anyway, you may be interested in <strong>multi-agent RL.</strong> <a href="https://www.marl-book.com/download/marl-book.pdf" rel="nofollow noreferrer">This book</a> looks good, but I only skimmed through it.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-10-18T11:59:19.890Z
Answers.Text: I would personally say that the link between RL and MDPs is stronger. Most theoretical results in RL assume an MDP, and the terminology describing MDPs is also core terminology in RL. However, yes RL techniques can be adapted and used in environments that are not strictly MDPs.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-10-18T09:43:00.317Z
Answers.LastActivityDate: 2024-10-18T09:43:00.317Z
Answers.UserDisplayName: nbro
Answers.Body: <p>Multi-armed bandits are MDPs composed of a single timestep and a single state, so they indeed fit the RL formulation, though it allows for more general settings.</p>
  <p>RL does not deal (naively) with multi-agent settings, but it can be used to approximate solutions. However, in such settings, you usually back the approach using Markov Games, Decentralized POMDPs or Mean Field Games, instead of MDPs</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-10-13T13:32:45.300Z
Answers.LastActivityDate: 2024-10-13T13:32:45.300Z
Answers.UserDisplayName: Alberto
Answers.Body: <p>MDPs do an excellent job of modeling most problems.</p>
  <p>One-arm bandits are MDPs with a single state, and every action returns to that state. The natural extension contextual bandits have multiple states chosen stochastically by the bandit and look even more like MDPs.</p>
  <p>Similar to a contextual bandit, multi-player games can often be modeled as an MDP in which the player has limited control of the next state. For a player, the other players exist in the transitions. The player chooses an action, and the other players determine the resulting state. In an MDP, this looks like a probability of transitioning to each resulting state.</p>
  <p>Our hope in RL is that the input can somehow help an agent maximize its reward in an environment.  MDPs can be a convenient way to consider how this might happen, but they are not required.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2024-10-13T15:51:16.687Z
Answers.LastActivityDate: 2024-10-13T15:51:16.687Z
Answers.UserDisplayName: foreverska
Body: <p>I am confused about the theoretical framework of reinforcement learning. For supervised learning, there seems to be a clear theoretical framework, e.g. as described by Wikipedia <a href="https://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work" rel="nofollow noreferrer">here</a>. I am unclear about a similar framework for RL.</p>
  <p>It seems that MDPs are baked into typical introduction to RL courses and theoretical descriptions of RL in the literature. However, certain problems that are also considered under RL don't seem to fit this: the multi-arm bandit problem, for example (or more practically, maybe RLHF), is often considered as a RL problem but doesn't fit the MDP model well (although I guess they can be modeled as a MDP with just 1 timestep); some RL problems, like 2-player games, don't seem to be able to be modeled under the typical RL MDP setup at all.</p>
  <p>Is there a theoretical RL framework that encapsulates everything?</p>
  
Tags: <reinforcement-learning><markov-decision-process><multi-agent-rl>
Title: How do 2-player games fit under the MDP framework of reinforcement learning?
UserDisplayName: Joe C.
ThreadText: # How do 2-player games fit under the MDP framework of reinforcement learning?
  
  (Asked by: username_0 on 2024-10-13)
  
  I am confused about the theoretical framework of reinforcement learning. For supervised learning, there seems to be a clear theoretical framework, e.g. as described by Wikipedia [here](https://en.wikipedia.org/wiki/Supervised_learning#How_supervised_learning_algorithms_work). I am unclear about a similar framework for RL.
  
  It seems that MDPs are baked into typical introduction to RL courses and theoretical descriptions of RL in the literature. However, certain problems that are also considered under RL don't seem to fit this: the multi-arm bandit problem, for example (or more practically, maybe RLHF), is often considered as a RL problem but doesn't fit the MDP model well (although I guess they can be modeled as a MDP with just 1 timestep); some RL problems, like 2-player games, don't seem to be able to be modeled under the typical RL MDP setup at all.
  
  Is there a theoretical RL framework that encapsulates everything?
  
  **Tags:** reinforcement-learning, markov-decision-process, multi-agent-rl
  
  ---
  
  ## 3 answers
  
  ### Answer by username_1 on 2024-10-18. Score: 2
  
  RL is not limited to MDPs, but standard textbooks will probably start with that because the most common RL algorithms (like Q-learning) assume an MDP. So, an MDP is just a way to **model** the environment. RL is the way you learn in that environment and RL is just a **trial-and-error approach to learning**, where you get feedback (reinforcement) for your actions, but you can also solve MDPs with dynamic programming (see policy iteration).
  
  You can model multi-agent systems with Markov Games (aka Stochastic Games), which are a simple generalisation of MDPs. See [my blog post](https://nbro.gitlab.io/blogging/2024/03/17/mdps-are-markov-games/).
  
  There are also other models, like **PO**MDPs, which are a generalisation of MDPs for other scenarios, in this case, **p**artially **o**bservable environments, i.e. you don't know exactly the state you're in.
  
  So, you can model your problem in different ways. Some problems may be modelled with MDPs, but the states may not be really fully observable, it's just an approximation. Sometimes it works. Take a look at the original DQN paper, where they tried to approximate states with a sequence of images.
  
  Anyway, you may be interested in **multi-agent RL.** [This book](https://www.marl-book.com/download/marl-book.pdf) looks good, but I only skimmed through it.
  
  > **Comments:**
  > **username_2**: I would personally say that the link between RL and MDPs is stronger. Most theoretical results in RL assume an MDP, and the terminology describing MDPs is also core terminology in RL. However, yes RL techniques can be adapted and used in environments that are not strictly MDPs.  
  
  ---
  
  ### Answer by username_3 on 2024-10-13. Score: 1
  
  Multi-armed bandits are MDPs composed of a single timestep and a single state, so they indeed fit the RL formulation, though it allows for more general settings.
  
  RL does not deal (naively) with multi-agent settings, but it can be used to approximate solutions. However, in such settings, you usually back the approach using Markov Games, Decentralized POMDPs or Mean Field Games, instead of MDPs
  
  
  ---
  
  ### Answer by username_4 on 2024-10-13. Score: 1
  
  MDPs do an excellent job of modeling most problems.
  
  One-arm bandits are MDPs with a single state, and every action returns to that state. The natural extension contextual bandits have multiple states chosen stochastically by the bandit and look even more like MDPs.
  
  Similar to a contextual bandit, multi-player games can often be modeled as an MDP in which the player has limited control of the next state. For a player, the other players exist in the transitions. The player chooses an action, and the other players determine the resulting state. In an MDP, this looks like a probability of transitioning to each resulting state.
  
  Our hope in RL is that the input can somehow help an agent maximize its reward in an environment. MDPs can be a convenient way to consider how this might happen, but they are not required.
  
  
  ---
  
  