Body: <p>I've read in <a href="https://stackoverflow.com/q/5215856/3924118">this</a> discussion that &quot;reinforcement learning is a way of finding the value function of a <a href="https://en.wikipedia.org/wiki/Markov_decision_process" rel="nofollow noreferrer">Markov Decision Process</a>&quot;.</p>
  <p>I want to implement an RL model, whose state space and action space dimensions would increase, as the MDP progresses. But I don't know how to define it it terms of e.g. Q-learning or some similar method.</p>
  <p>Precisely, I want to create a model, that would generate <a href="https://en.wikipedia.org/wiki/Boolean_circuit" rel="nofollow noreferrer">boolean circuits</a>. At each step, it could perform four different actions:</p>
  <ul>
  <li>apply <span class="math-container">$AND$</span> gate on two wires,</li>
  <li>apply <span class="math-container">$OR$</span> gate on two wires,</li>
  <li>apply <span class="math-container">$NOT$</span> gate on one wire,</li>
  <li>add new wire.</li>
  </ul>
  <p>Each of the first three actions could be performed on any currently available wires (targets). Also, the number of wires will change over time. It might increase if we perform fourth action, or decrese after e.g. application of an <span class="math-container">$AND$</span> gate (taking as input two wires and outputting just one).</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T17:23:34.750Z
Comments.Text: It's not fully clear to me what you mean by "targets" here. Can you clarify that?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T19:23:04.323Z
Comments.Text: Action $a_0$ might be for example an AND gate and targets would be specific circuits representing bits. So AND action would act on two targets - bits, while e.g. NOT action would act just on one target.
Comments.UserDisplayName: brzepkowski
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T20:31:10.200Z
Comments.Text: I still don't get what is a target in RL terms. What would a target correspond to in RL or MDPs?
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T20:50:56.203Z
Comments.Text: @nbro: My understanding is that the possible targets are part of the state, and both the state space and action space dimensions may increase as the MDP progresses.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T21:45:25.077Z
Comments.Text: @NeilSlater That's exactly what I wanted to say, but I couldn't formulate it as clearly as you did. I edited my question.
Comments.UserDisplayName: brzepkowski
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T21:54:37.553Z
Comments.Text: @brzepkowski It may be a good idea to describe the exact problem you're trying to solve with RL. That will provide some more context and clarity, although the question is now is clearer.
Comments.UserDisplayName: nbro
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-12T22:14:50.647Z
Comments.Text: I suggest keep the mention of actions that add "targets" and the need to specify which target to work with in each action. If there is any important constraint on targets - a maximum number allowed, or that they must be arranged in a graph or in a discrete space (like a grid) that may be worth mentioning.
Comments.UserDisplayName: Neil Slater
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2020-12-15T08:59:22.287Z
Comments.Text: I added the precise description of what I want to achieve.
Comments.UserDisplayName: brzepkowski
Tags: <reinforcement-learning><action-spaces><discrete-action-spaces>
Title: How to implement RL model with increasing dimensions of state space and action space?
UserDisplayName: brzepkowski
ThreadText: # How to implement RL model with increasing dimensions of state space and action space?
  
  (Asked by: username_0 on 2020-12-12)
  
  I've read in [this](https://stackoverflow.com/q/5215856/3924118) discussion that "reinforcement learning is a way of finding the value function of a [Markov Decision Process](https://en.wikipedia.org/wiki/Markov_decision_process)".
  
  I want to implement an RL model, whose state space and action space dimensions would increase, as the MDP progresses. But I don't know how to define it it terms of e.g. Q-learning or some similar method.
  
  Precisely, I want to create a model, that would generate [boolean circuits](https://en.wikipedia.org/wiki/Boolean_circuit). At each step, it could perform four different actions:
  
  * apply $AND$ gate on two wires,
  * apply $OR$ gate on two wires,
  * apply $NOT$ gate on one wire,
  * add new wire.
  
  Each of the first three actions could be performed on any currently available wires (targets). Also, the number of wires will change over time. It might increase if we perform fourth action, or decrese after e.g. application of an $AND$ gate (taking as input two wires and outputting just one).
  
  **Tags:** reinforcement-learning, action-spaces, discrete-action-spaces
  > **Comments:**
  > **username_1**: It's not fully clear to me what you mean by "targets" here. Can you clarify that?  
  > **username_0**: Action $a_0$ might be for example an AND gate and targets would be specific circuits representing bits. So AND action would act on two targets - bits, while e.g. NOT action would act just on one target.  
  > **username_1**: I still don't get what is a target in RL terms. What would a target correspond to in RL or MDPs?  
  > **username_2**: @nbro: My understanding is that the possible targets are part of the state, and both the state space and action space dimensions may increase as the MDP progresses.  
  > **username_0**: @NeilSlater That's exactly what I wanted to say, but I couldn't formulate it as clearly as you did. I edited my question.  
  > **username_1**: @brzepkowski It may be a good idea to describe the exact problem you're trying to solve with RL. That will provide some more context and clarity, although the question is now is clearer.  
  > **username_2**: I suggest keep the mention of actions that add "targets" and the need to specify which target to work with in each action. If there is any important constraint on targets - a maximum number allowed, or that they must be arranged in a graph or in a discrete space (like a grid) that may be worth mentioning.  
  > **username_0**: I added the precise description of what I want to achieve.  
  
  ---
  
  ## 0 answers
  
  