Answers.Body: <blockquote>
  <p>Is it possible to make the transition function change as the game progress?</p>
  </blockquote>
  <p>Yes, the normal way to do this would be to make the current time or time step <span class="math-container">$t$</span> part of the state <span class="math-container">$s$</span>, so that equation 1 or 2 applies as normal. Similar applies if by &quot;as the game progresses&quot; that there is some other measure of progression such as how much the agent has scored so far, make that measure part of the state. Unless for some reason you do not want to allow the agent to track this extra pogression effect that impacts the behaviour - in which case you would typically consider the environment to be a partially observable MPD or POMDP.</p>
  <p>Your equation 3 doesn't define a dynamic environment, but a parametric one. You have added the parameter <span class="math-container">$x$</span> to the normal MDP transition function. What that means depends critically on how the parametrisation of the transition function <span class="math-container">$T$</span> works in detail, and what you then do with the parameter <span class="math-container">$x$</span>. Different modes of changing <span class="math-container">$x$</span> (plus different sensitivies to <span class="math-container">$x$</span> in the transtion function <span class="math-container">$T$</span>) correspond to different classes of environment in the RL literature.</p>
  <p>Here are some examples:</p>
  <ul>
  <li><p>If <span class="math-container">$x$</span> is sampled from set <span class="math-container">$X$</span> once, and once only, your equation 3 reduces to equation 2. Sampling <span class="math-container">$x$</span> corresponds to selecting an environment to learn.</p>
  </li>
  <li><p>If <span class="math-container">$x$</span> is known/accessible to the agent, then regardless of how it is chosen, your true state is <span class="math-container">$s+x$</span> and equation 3 reduces to either equation 1 or equation 2 depending on how the <span class="math-container">$x$</span> part of <span class="math-container">$s+x$</span> transitions.</p>
  </li>
  <li><p>If <span class="math-container">$x$</span> is sampled independently from any other variable, on each and every time step, then equation 3 reduces to equation 1. Sampling <span class="math-container">$x$</span> in this way corresponds to choosing a random transition (from whatever is allowed by the nature of <span class="math-container">$T$</span>) based on state and action.</p>
  </li>
  <li><p>If <span class="math-container">$x$</span> is sampled infrequently (less than once per episode) or evolves in a slow fashion (when combined with how T works, changes happen to effective transition rules less than once per episode), then you may have a non-stationary environment. This is typically addressed by continuously learning agents - a good example of an RL method written specifically to address this is DynaQ+.</p>
  </li>
  <li><p>If <span class="math-container">$x$</span> is sampled (or even fixed) at the start of the episode and evolves either independently or depending on state <span class="math-container">$s$</span> and action <span class="math-container">$a$</span> (plus any random changes), and the agent is not allowed to know <span class="math-container">$x$</span>, then you have a POMDP. How solvable that is depends on how easy it is for the agent to allow for and learn what it can about <span class="math-container">$x$</span> - you may specifically need a POMDP solver. Knowing <span class="math-container">$X$</span> and the transition rules for <span class="math-container">$x$</span> may make a POMDP solver more feasible in practice.</p>
  <ul>
  <li>Instead of using <span class="math-container">$s$</span> and <span class="math-container">$x$</span>, literature on POMDPs would typically use <span class="math-container">$s$</span> for state (equivalent to your <span class="math-container">$s, x$</span> concatenated) and <span class="math-container">$o$</span> for the agent's observation (equivalent to your <span class="math-container">$s$</span>)</li>
  </ul>
  </li>
  </ul>
  <p>So, in summary, there isn't really a class of &quot;dynamic&quot; environments in RL studied under that name. Your idea might fit into one or more of several other well-studied concepts in RL instead.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-05-26T19:14:21.643Z
Answers.LastActivityDate: 2022-05-26T21:35:22.990Z
Answers.LastEditDate: 2022-05-26T21:35:22.990Z
Answers.UserDisplayName: Neil Slater
Body: <p>In general, there are two types of transition functions in reinforcement learning. Mathematically, they are as follows</p>
  <p>#1: Stochastic state transition function:</p>
  <p><span class="math-container">$$T : S \times A \times S \rightarrow  [0, 1]$$</span></p>
  <p>#2: Deterministic state transition function:</p>
  <p><span class="math-container">$$T : S \times A \rightarrow  S$$</span></p>
  <p>Is it possible to make the transition function change as the game progress? Or is it impossible to assume such a transition function as it cannot qualify to be a function?</p>
  <p>Or in other words, I may want to introduce something as follows:</p>
  <p>#3: Dynamic state transition function:</p>
  <p><span class="math-container">$$T : S \times A \times X \rightarrow  S$$</span></p>
  <p>where <span class="math-container">$X$</span> is some continuous set.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T09:33:57.643Z
Comments.Text: Maybe you're looking for a non-stationary MDP? In that case, $T$ can change over time, i.e. it's non-stationary. If this answers your question, I will write it below. But maybe you should explain why you're asking this question. Why would $X$ be continuous?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T10:22:47.713Z
Comments.Text: Yeah, @nbro I think that it is an exact answer. Please write it if possible. I formulated #3 just to make $T$ a function and the continuous assumption is to show some underlying randomness. I mean, the next state may change for a combination of the present state and action if episodes are repeated.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T15:42:46.770Z
Comments.Text: Are you able to specify what $X$ can depend on? Non-stationary MDPs usually requires that the dynamics of $X$ will depend solely on time, and if you expect to have any chance of learning them, also that progression of $T$ due to changing $X$ is relatively slow (or if radical then infrequent, thus slow when averaged over many episodes). Your generic description of $T$ could also be used to describe POMDPs - when $X$ depends on some unobservable data - and possibly other scenarios too, so  it is worth clarifying.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:21:58.633Z
Comments.Text: @NeilSlater We can assume $X$ as continuous  random vector obeying a probability distribution.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:30:11.340Z
Comments.Text: @hanugm: That's not dynamic, that's stochastic and no different to your first equation. The only way it could be dynamic is if $X$ was correlated to some data relevant to the environment (e.g. when the experiment was run).
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:45:32.167Z
Comments.Text: @NeilSlater How is it the same as the first one as $X$ are $S$ are entirely different?
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:45:34.533Z
Comments.Text: @hanugm: Actually I assumed in my last comment that $X$ is sampled once per time step. If it is sampled less frequently there would be different characterisations. But how often it is sampled, and how radical the changes are to $T$ - plus whether $X$ correlates with anything meaningful about the problem are critical pieces of information for any practical approach. In *general*, if you are not willing to define anything about $X$ or $T$, then your problem is not usefully an MDP and very little RL theory could be applied to it.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:48:06.783Z
Comments.Text: @NeilSlater So, if $X$ is independent or has an infinitesimal correlation to the environment states then can't I expect any RL algorithm to work on my environment?
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:50:39.523Z
Comments.Text: @hanugm: No. It depends on how/when you are sampling $X$. If it is sampled every time step, then equation 1 and equation 3 describe the same thing - every combination of S, A has some probability of transitioning to the next state S'.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:51:06.070Z
Comments.Text: If you are doing something else with $X$, well it depends on precisely *what* you are doing.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:51:54.563Z
Comments.Text: @NeilSlater Suppose the environment states is for automatic driving car and $X$ is from the dataset of cat images.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:53:36.663Z
Comments.Text: OK, let's suppose that. When do you sample from $X$ (to get a specific cat picture $x$), and how does $T$ process the combination $(s, a, x)$ to produce the next car state?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:56:04.167Z
Comments.Text: @NeilSlater I edited the comment with a continuous one, chess is discrete. I use to map some cat image, which does not depend on the state of the actual environment and  define a function.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:56:45.810Z
Comments.Text: I matched your edit :-) I don't think continuous vs discrete makes any difference here.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T16:58:06.507Z
Comments.Text: @NeilSlater ha. Theoretically, can't I define a custom mapping? For suppose, I pass $(s, a,x)$ to a neural network, whose output dimension is the same as the state space and pick the next $s'$ which has a minimum Euclidean distance with the output of the neural network.
Comments.UserDisplayName: hanugm
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2022-05-26T17:43:54.607Z
Comments.Text: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/136605/discussion-between-neil-slater-and-hanugm).
Comments.UserDisplayName: Neil Slater
Tags: <reinforcement-learning><markov-decision-process><transition-model>
Title: Can the state transition function be dynamic in reinforcement learning?
UserDisplayName: hanugm
ThreadText: # Can the state transition function be dynamic in reinforcement learning?
  
  (Asked by: username_0 on 2022-05-26)
  
  In general, there are two types of transition functions in reinforcement learning. Mathematically, they are as follows
  
  #1: Stochastic state transition function:
  
  $$T : S \times A \times S \rightarrow [0, 1]$$
  
  #2: Deterministic state transition function:
  
  $$T : S \times A \rightarrow S$$
  
  Is it possible to make the transition function change as the game progress? Or is it impossible to assume such a transition function as it cannot qualify to be a function?
  
  Or in other words, I may want to introduce something as follows:
  
  #3: Dynamic state transition function:
  
  $$T : S \times A \times X \rightarrow S$$
  
  where $X$ is some continuous set.
  
  **Tags:** reinforcement-learning, markov-decision-process, transition-model
  > **Comments:**
  > **username_1**: Maybe you're looking for a non-stationary MDP? In that case, $T$ can change over time, i.e. it's non-stationary. If this answers your question, I will write it below. But maybe you should explain why you're asking this question. Why would $X$ be continuous?  
  > **username_0**: Yeah, @nbro I think that it is an exact answer. Please write it if possible. I formulated #3 just to make $T$ a function and the continuous assumption is to show some underlying randomness. I mean, the next state may change for a combination of the present state and action if episodes are repeated.  
  > **username_2**: Are you able to specify what $X$ can depend on? Non-stationary MDPs usually requires that the dynamics of $X$ will depend solely on time, and if you expect to have any chance of learning them, also that progression of $T$ due to changing $X$ is relatively slow (or if radical then infrequent, thus slow when averaged over many episodes). Your generic description of $T$ could also be used to describe POMDPs - when $X$ depends on some unobservable data - and possibly other scenarios too, so  it is worth clarifying.  
  > **username_0**: @NeilSlater We can assume $X$ as continuous  random vector obeying a probability distribution.  
  > **username_2**: @hanugm: That's not dynamic, that's stochastic and no different to your first equation. The only way it could be dynamic is if $X$ was correlated to some data relevant to the environment (e.g. when the experiment was run).  
  > **username_0**: @NeilSlater How is it the same as the first one as $X$ are $S$ are entirely different?  
  > **username_2**: @hanugm: Actually I assumed in my last comment that $X$ is sampled once per time step. If it is sampled less frequently there would be different characterisations. But how often it is sampled, and how radical the changes are to $T$ - plus whether $X$ correlates with anything meaningful about the problem are critical pieces of information for any practical approach. In *general*, if you are not willing to define anything about $X$ or $T$, then your problem is not usefully an MDP and very little RL theory could be applied to it.  
  > **username_0**: @NeilSlater So, if $X$ is independent or has an infinitesimal correlation to the environment states then can't I expect any RL algorithm to work on my environment?  
  > **username_2**: @hanugm: No. It depends on how/when you are sampling $X$. If it is sampled every time step, then equation 1 and equation 3 describe the same thing - every combination of S, A has some probability of transitioning to the next state S'.  
  > **username_2**: If you are doing something else with $X$, well it depends on precisely *what* you are doing.  
  > **username_0**: @NeilSlater Suppose the environment states is for automatic driving car and $X$ is from the dataset of cat images.  
  > **username_2**: OK, let's suppose that. When do you sample from $X$ (to get a specific cat picture $x$), and how does $T$ process the combination $(s, a, x)$ to produce the next car state?  
  > **username_0**: @NeilSlater I edited the comment with a continuous one, chess is discrete. I use to map some cat image, which does not depend on the state of the actual environment and  define a function.  
  > **username_2**: I matched your edit :-) I don't think continuous vs discrete makes any difference here.  
  > **username_0**: @NeilSlater ha. Theoretically, can't I define a custom mapping? For suppose, I pass $(s, a,x)$ to a neural network, whose output dimension is the same as the state space and pick the next $s'$ which has a minimum Euclidean distance with the output of the neural network.  
  > **username_2**: Let us [continue this discussion in chat](https://chat.stackexchange.com/rooms/136605/discussion-between-neil-slater-and-hanugm).  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2022-05-26. Score: 1
  
  > Is it possible to make the transition function change as the game progress?
  
  Yes, the normal way to do this would be to make the current time or time step $t$ part of the state $s$, so that equation 1 or 2 applies as normal. Similar applies if by "as the game progresses" that there is some other measure of progression such as how much the agent has scored so far, make that measure part of the state. Unless for some reason you do not want to allow the agent to track this extra pogression effect that impacts the behaviour - in which case you would typically consider the environment to be a partially observable MPD or POMDP.
  
  Your equation 3 doesn't define a dynamic environment, but a parametric one. You have added the parameter $x$ to the normal MDP transition function. What that means depends critically on how the parametrisation of the transition function $T$ works in detail, and what you then do with the parameter $x$. Different modes of changing $x$ (plus different sensitivies to $x$ in the transtion function $T$) correspond to different classes of environment in the RL literature.
  
  Here are some examples:
  
  * If $x$ is sampled from set $X$ once, and once only, your equation 3 reduces to equation 2. Sampling $x$ corresponds to selecting an environment to learn.
  * If $x$ is known/accessible to the agent, then regardless of how it is chosen, your true state is $s+x$ and equation 3 reduces to either equation 1 or equation 2 depending on how the $x$ part of $s+x$ transitions.
  * If $x$ is sampled independently from any other variable, on each and every time step, then equation 3 reduces to equation 1. Sampling $x$ in this way corresponds to choosing a random transition (from whatever is allowed by the nature of $T$) based on state and action.
  * If $x$ is sampled infrequently (less than once per episode) or evolves in a slow fashion (when combined with how T works, changes happen to effective transition rules less than once per episode), then you may have a non-stationary environment. This is typically addressed by continuously learning agents - a good example of an RL method written specifically to address this is DynaQ+.
  * If $x$ is sampled (or even fixed) at the start of the episode and evolves either independently or depending on state $s$ and action $a$ (plus any random changes), and the agent is not allowed to know $x$, then you have a POMDP. How solvable that is depends on how easy it is for the agent to allow for and learn what it can about $x$ - you may specifically need a POMDP solver. Knowing $X$ and the transition rules for $x$ may make a POMDP solver more feasible in practice.
  
    + Instead of using $s$ and $x$, literature on POMDPs would typically use $s$ for state (equivalent to your $s, x$ concatenated) and $o$ for the agent's observation (equivalent to your $s$)
  
  So, in summary, there isn't really a class of "dynamic" environments in RL studied under that name. Your idea might fit into one or more of several other well-studied concepts in RL instead.
  
  
  ---
  
  