Answers.Body: <blockquote>
  <p>I'm not sure how to model this as an MDP.</p>
  </blockquote>
  <p>You have defined a fixed set of actions, and I think from your statements that the environment is deterministic (same sequence of actions from start state returns the same reward). In addition, there is no observational state data available to the agent.</p>
  <p>The reward depends on the sequence of actions <em>somehow</em>, and reliably. That makes the <em>full</em> history of actions the only thing that can be used to describe the state, and it does so perfectly. Aside: The rest of the advice here applies even if the reward function or unobservable state is not deterministic - although your problem may become impossible to solve in that case depending on degree of randomness.</p>
  <p>Your state is therefore the vector of actions so far, and your state space size is <span class="math-container">$(|\mathcal{A}|+1)^M$</span> where <span class="math-container">$M$</span> is the maximum sequence length you want to consider. The <span class="math-container">$+1$</span> is because shorter, truncated sequences are full states. With this state, you have a full MDP model: An environment with states, actions, rewards and transition rules for states (append action to state vector).</p>
  <p>Without anything to base a belief model on for the agent to guess at some internal state, I don't think there is any opportunity to use a formal POMDP model.</p>
  <p>You could approximate value functions, possibly usefully, by using a deep recurrent neural network, fed actions one at a time as a sequence, and that <em>might</em> learn to generalise predicting action values from sampling trials. How successful this is will depend on how the rewards are structured in practice. You have stated that you would prefer not to do this, but it might be something that makes the scale practical.</p>
  <p>Other approximation schemes are possible - anything that reduces down the action history to a smaller or simpler space could work. For a discrete approximation you could use a table for Q values, for a continuous one you could use a linear regression to learn weights that predict Q values. For example, a continuous summary that is a vector the size of the action space, where taking an action multiplies the whole vector by a decay factor, then adds 1 to the element matching the action would work in a linear model. However, although this definitely summarises the sequence into a more manageable space, you have nothing from the environment to base this on, it would just be a guess at a useful summary. From your examples I don't think such a summary would have a linear relationship to action values, so you would again need a neural network for deep RL in order to make good use of it.</p>
  <p>It is far from clear whether RL is a useful system to discover optimal sequences in your environment. Other than RL, simple combinatorial searches could be effective. Which is better will depend on how reward patterns are distributed. Most RL will tend to search between randomly or focused close to best rewards seen so far. It is not clear from your description whether that would be the most effective search strategy. Exhaustive breadth- or depth- based searches could easily be more effective.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2023-08-23T18:34:47.470Z
Answers.LastActivityDate: 2023-08-23T20:58:11.177Z
Answers.LastEditDate: 2023-08-23T20:58:11.177Z
Answers.UserDisplayName: Neil Slater
Body: <p>I would like to build an RL agent who's objective is to find an N length sequence of actions to a reward where N is not known and the states are indistinguishable from each other (at least for it's sensors).  All actions are available in all states.</p>
  <p>For example it's goal may to find the sequence [1, 2] in the action space {1, 2, 3, 4, 5}.  Or even [1, 2, 1, 2] where the chief reward only comes from the state at the end of the fourth transition.  I expect the sequences to be much longer and there to be rewards at some states along many sequences but one chief reward at the end of one or more &quot;correct&quot; sequences.</p>
  <p>I'm not sure how to model this as an MDP.  Each action in a sequence feels like it belongs in it's own state.  But given I am not sure how many items are in a sequence I'm not sure what to do other than have an empty table large enough to support most sequences and proceed with POMDP.</p>
  <p>I am attempting to avoid anything deep (like Neural networks).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T15:52:46.523Z
Comments.Text: By "the states are indistinguishable from each other" do you mean that there is literally no data available to the agent other than the history of its actions? Is there actually some hidden state that the agent cannot see? Is there a termination signal when the agent "completes" a sequence (or a special action to declare "I have completed the sequence")?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T16:14:45.207Z
Comments.Text: The agent knows it's history and has a reward signal.  At this time I am assuming it is otherwise in the dark.  The agent has no idea what states exist.  A sufficiently high reward marks a completed sequence.  It can be assumed that once this state is reached, the same sequence entered again will arrive back at this state.
Comments.UserDisplayName: foreverska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T16:17:53.550Z
Comments.Text: Does the agent know (or is told) when it receives a "sufficiently high" reward? If it misses it, can it in theory continue forever, generating an infinite low-scoring sequence?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T16:20:48.483Z
Comments.Text: Is there any similarity between "good" sequences, that could be learned? Or are the good sequences effectively randomly scattered in sequence space as far as the agent is concerned?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T16:33:32.857Z
Comments.Text: We can assume to know what sufficiently high means in this case.  There is likely similarity between good sequences.  Even, if the sequence was [1, 5, 3] x 5, at each 3 in that sequence it might receive a small reward. [4, 1, 5, 3, 2] may give a small reward on both 3 and 2.  Finally [2, 2, 3] may give a reward where [2, 2, 3] x 5 does not give a sufficiently high reward.
Comments.UserDisplayName: foreverska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T17:44:08.573Z
Comments.Text: What happens when the agent does not receive a "sufficiently high" reward? Can any assumption be made about maximum sequence length, and the agent give up?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T17:53:00.120Z
Comments.Text: The theoretical existence of a sufficiently high reward following a sequence of N would necessitate that there is a finite number M where N <= M.  If the agent interacts with an environment M times, I could accept a simplifying assumption that it goes back to the beginning with no reward.
Comments.UserDisplayName: foreverska
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T18:10:16.527Z
Comments.Text: By "I am attempting to avoid anything deep." you mean you prefer to avoid neural networks?
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-08-23T18:16:51.467Z
Comments.Text: That is correct.  I recognize that a NN can estimate a complex state/transition/Q value relationship.  I'm looking for other solutions.
Comments.UserDisplayName: foreverska
Tags: <reinforcement-learning><markov-decision-process>
Title: MDP to model finding an optimal sequence of actions with no other state data
UserDisplayName: foreverska
ThreadText: # MDP to model finding an optimal sequence of actions with no other state data
  
  (Asked by: username_0 on 2023-08-23)
  
  I would like to build an RL agent who's objective is to find an N length sequence of actions to a reward where N is not known and the states are indistinguishable from each other (at least for it's sensors). All actions are available in all states.
  
  For example it's goal may to find the sequence [1, 2] in the action space {1, 2, 3, 4, 5}. Or even [1, 2, 1, 2] where the chief reward only comes from the state at the end of the fourth transition. I expect the sequences to be much longer and there to be rewards at some states along many sequences but one chief reward at the end of one or more "correct" sequences.
  
  I'm not sure how to model this as an MDP. Each action in a sequence feels like it belongs in it's own state. But given I am not sure how many items are in a sequence I'm not sure what to do other than have an empty table large enough to support most sequences and proceed with POMDP.
  
  I am attempting to avoid anything deep (like Neural networks).
  
  **Tags:** reinforcement-learning, markov-decision-process
  > **Comments:**
  > **username_1**: By "the states are indistinguishable from each other" do you mean that there is literally no data available to the agent other than the history of its actions? Is there actually some hidden state that the agent cannot see? Is there a termination signal when the agent "completes" a sequence (or a special action to declare "I have completed the sequence")?  
  > **username_0**: The agent knows it's history and has a reward signal.  At this time I am assuming it is otherwise in the dark.  The agent has no idea what states exist.  A sufficiently high reward marks a completed sequence.  It can be assumed that once this state is reached, the same sequence entered again will arrive back at this state.  
  > **username_1**: Does the agent know (or is told) when it receives a "sufficiently high" reward? If it misses it, can it in theory continue forever, generating an infinite low-scoring sequence?  
  > **username_1**: Is there any similarity between "good" sequences, that could be learned? Or are the good sequences effectively randomly scattered in sequence space as far as the agent is concerned?  
  > **username_0**: We can assume to know what sufficiently high means in this case.  There is likely similarity between good sequences.  Even, if the sequence was [1, 5, 3] x 5, at each 3 in that sequence it might receive a small reward. [4, 1, 5, 3, 2] may give a small reward on both 3 and 2.  Finally [2, 2, 3] may give a reward where [2, 2, 3] x 5 does not give a sufficiently high reward.  
  > **username_1**: What happens when the agent does not receive a "sufficiently high" reward? Can any assumption be made about maximum sequence length, and the agent give up?  
  > **username_0**: The theoretical existence of a sufficiently high reward following a sequence of N would necessitate that there is a finite number M where N <= M.  If the agent interacts with an environment M times, I could accept a simplifying assumption that it goes back to the beginning with no reward.  
  > **username_1**: By "I am attempting to avoid anything deep." you mean you prefer to avoid neural networks?  
  > **username_0**: That is correct.  I recognize that a NN can estimate a complex state/transition/Q value relationship.  I'm looking for other solutions.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2023-08-23. Score: 2 | Accepted answer
  
  > I'm not sure how to model this as an MDP.
  
  You have defined a fixed set of actions, and I think from your statements that the environment is deterministic (same sequence of actions from start state returns the same reward). In addition, there is no observational state data available to the agent.
  
  The reward depends on the sequence of actions *somehow*, and reliably. That makes the *full* history of actions the only thing that can be used to describe the state, and it does so perfectly. Aside: The rest of the advice here applies even if the reward function or unobservable state is not deterministic - although your problem may become impossible to solve in that case depending on degree of randomness.
  
  Your state is therefore the vector of actions so far, and your state space size is $(|\mathcal{A}|+1)^M$ where $M$ is the maximum sequence length you want to consider. The $+1$ is because shorter, truncated sequences are full states. With this state, you have a full MDP model: An environment with states, actions, rewards and transition rules for states (append action to state vector).
  
  Without anything to base a belief model on for the agent to guess at some internal state, I don't think there is any opportunity to use a formal POMDP model.
  
  You could approximate value functions, possibly usefully, by using a deep recurrent neural network, fed actions one at a time as a sequence, and that *might* learn to generalise predicting action values from sampling trials. How successful this is will depend on how the rewards are structured in practice. You have stated that you would prefer not to do this, but it might be something that makes the scale practical.
  
  Other approximation schemes are possible - anything that reduces down the action history to a smaller or simpler space could work. For a discrete approximation you could use a table for Q values, for a continuous one you could use a linear regression to learn weights that predict Q values. For example, a continuous summary that is a vector the size of the action space, where taking an action multiplies the whole vector by a decay factor, then adds 1 to the element matching the action would work in a linear model. However, although this definitely summarises the sequence into a more manageable space, you have nothing from the environment to base this on, it would just be a guess at a useful summary. From your examples I don't think such a summary would have a linear relationship to action values, so you would again need a neural network for deep RL in order to make good use of it.
  
  It is far from clear whether RL is a useful system to discover optimal sequences in your environment. Other than RL, simple combinatorial searches could be effective. Which is better will depend on how reward patterns are distributed. Most RL will tend to search between randomly or focused close to best rewards seen so far. It is not clear from your description whether that would be the most effective search strategy. Exhaustive breadth- or depth- based searches could easily be more effective.
  
  
  ---
  
  