Answers.Body: <p>Discretizing state/action space will always be a very expensive strategy, in fact I don't think you can do better than exponential time in state/action dimension that way.</p>
  <p>Now, you still haven't really explained your algorithm with the discretized states and actions. Given your known models, it sounds like you're planning on doing dynamic programming. This would definitely be an exponential time algorithm. You also haven't explained how you'd use your knowledge of the model in your policy gradient implementation. If you're just using it to sample some trajectories to have more data for updates, policy gradient methods will be much more efficient (poly-time). Otherwise, if you're planning on using your model for some sort of MCTS planning, depending on how you implement that, it could be very inefficient as well.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T15:24:35.760Z
Answers.Text: Thank you for the respond, I agree if I discretize the state space it will be exponential time. And what's really costly is the optimization part, since I do not really know the shape of the function.  So I have to choose my optimizer carefully.
Answers.UserDisplayName: leodongxu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T15:25:29.523Z
Answers.Text: And indeed, my knowledge of the model is used to simulate the some trajectories in order to update my policy.
Answers.UserDisplayName: leodongxu
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-06-23T14:03:14.700Z
Answers.LastActivityDate: 2020-06-23T14:03:14.700Z
Answers.UserDisplayName: harwiltz
Body: <p><strong>Model Description</strong>: Model based (assume known of the entire model) <em>Markov decision process</em>.</p>
  <ul>
  <li>Time(<span class="math-container">$t$</span>): Finite horizon discrete time with discounting factor</li>
  <li>State(<span class="math-container">$x_t$</span>): Continuous multi-dimensional state</li>
  <li>Action(<span class="math-container">$a_t$</span>): Continuous multi-dimensional action (deterministic action)</li>
  <li>Feasible(possible action) (<span class="math-container">$A_t$</span>): possible action is a continuous multi-dimensional space, no discretization for the action space.</li>
  <li>Transition kernel(<span class="math-container">$P$</span>): known and have some randomness associated with the current state and next state</li>
  </ul>
  <p><strong>Reward function</strong>: known in explicit form and terminal reward is know.</p>
  <p><strong>The method I tried to solve the model:</strong>
  Discretize the state space and construct multi-dimensional grid for state space, starting from the terminal state, I used backward induction to reconstruct value function from the previous period. By using the <em>Bellman equation</em>, I need to solve an optimization problem, selecting the best action that gives me the best objective function.</p>
  <p><span class="math-container">$$V_t(x_t) = max_{a_t \in A_t}[R_t(x_t,a_t) + E[\tilde{V}_{t+1}(x_{t+1})|x_t, a_t]]$$</span></p>
  <p>where <span class="math-container">$\tilde{V}_{t+1}$</span> here is an approximation using <em>interpolation method</em>, since the discrete values are calculated from the previous time episode. In other words: <span class="math-container">$\tilde{V}_{t+1}$</span> is approximated by some discrete value: <span class="math-container">$$V_{t+1}(x_0),V_{t+1}(x_1),V_{t+1}(x_2)\cdots V_{t+1}(x_N)$$</span> where <span class="math-container">$x_0,x_1,x_2\cdots x_N$</span> are grid points from discretizing the state space.</p>
  <p>In this way, for every time steps <span class="math-container">$t$</span>, I could have a value function for every grid point and my value function could be approximated by using some interpolation method(probably cubic spline).</p>
  <p>But here are some of the problems:</p>
  <ol>
  <li>what kind of interpolation is suitable for high dimensional data.</li>
  <li>Say we have five dimension for the state, then I discretize the state by giving 5 grid points to every dimension, then there are <span class="math-container">$5^5 = 3125$</span> discrete state values I need to calculate through the optimization (curse of the dimensionality).</li>
  <li>What kind of optimizer should I use? Since I do not know the shape of the objective function, I do not know if it is a smooth function and I do not know if the function is concave. So I may have to use a <em>robust optimizer</em>, probably some <em>evolutionary optimizer</em>. So eventually I end up with this computational complexity and it takes too long for the computation.</li>
  </ol>
  <p>And recently I learned the techniques of <a href="https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html" rel="nofollow noreferrer">policy gradient from OpenAI</a>.
  This method avoids using this backward induction and approximating the value function by using interpolation. And obtained the approximated policy by firstly guessing a functional form of the policy and take approximated gradient of the policy function by using <code>sampling (simulation) method</code>. Since the model is known, every time it could sample new trajectories and use that to update the policy by using the <code>stochastic gradient assent</code> method. In this way updating the policy until it gets some sort of convergence.</p>
  <p>I am wondering if this type of technique could potentially reduce the computational complexity significantly. Any advice helps, thanks a lot.</p>
  
Tags: <reinforcement-learning><optimization><time-complexity><finite-markov-decision-process><interpolation>
Title: Continuous state and continuous action Markov decision process time complexity estimate: backward induction VS policy gradient method (RL)
UserDisplayName: leodongxu
ThreadText: # Continuous state and continuous action Markov decision process time complexity estimate: backward induction VS policy gradient method (RL)
  
  (Asked by: username_0 on 2020-06-22)
  
  **Model Description**: Model based (assume known of the entire model) *Markov decision process*.
  
  * Time($t$): Finite horizon discrete time with discounting factor
  * State($x\_t$): Continuous multi-dimensional state
  * Action($a\_t$): Continuous multi-dimensional action (deterministic action)
  * Feasible(possible action) ($A\_t$): possible action is a continuous multi-dimensional space, no discretization for the action space.
  * Transition kernel($P$): known and have some randomness associated with the current state and next state
  
  **Reward function**: known in explicit form and terminal reward is know.
  
  **The method I tried to solve the model:**
  Discretize the state space and construct multi-dimensional grid for state space, starting from the terminal state, I used backward induction to reconstruct value function from the previous period. By using the *Bellman equation*, I need to solve an optimization problem, selecting the best action that gives me the best objective function.
  
  $$V\_t(x\_t) = max\_{a\_t \in A\_t}[R\_t(x\_t,a\_t) + E[\tilde{V}\_{t+1}(x\_{t+1})|x\_t, a\_t]]$$
  
  where $\tilde{V}\_{t+1}$ here is an approximation using *interpolation method*, since the discrete values are calculated from the previous time episode. In other words: $\tilde{V}\_{t+1}$ is approximated by some discrete value: $$V\_{t+1}(x\_0),V\_{t+1}(x\_1),V\_{t+1}(x\_2)\cdots V\_{t+1}(x\_N)$$ where $x\_0,x\_1,x\_2\cdots x\_N$ are grid points from discretizing the state space.
  
  In this way, for every time steps $t$, I could have a value function for every grid point and my value function could be approximated by using some interpolation method(probably cubic spline).
  
  But here are some of the problems:
  
  1. what kind of interpolation is suitable for high dimensional data.
  2. Say we have five dimension for the state, then I discretize the state by giving 5 grid points to every dimension, then there are $5^5 = 3125$ discrete state values I need to calculate through the optimization (curse of the dimensionality).
  3. What kind of optimizer should I use? Since I do not know the shape of the objective function, I do not know if it is a smooth function and I do not know if the function is concave. So I may have to use a *robust optimizer*, probably some *evolutionary optimizer*. So eventually I end up with this computational complexity and it takes too long for the computation.
  
  And recently I learned the techniques of [policy gradient from OpenAI](https://spinningup.openai.com/en/latest/spinningup/rl_intro3.html).
  This method avoids using this backward induction and approximating the value function by using interpolation. And obtained the approximated policy by firstly guessing a functional form of the policy and take approximated gradient of the policy function by using `sampling (simulation) method`. Since the model is known, every time it could sample new trajectories and use that to update the policy by using the `stochastic gradient assent` method. In this way updating the policy until it gets some sort of convergence.
  
  I am wondering if this type of technique could potentially reduce the computational complexity significantly. Any advice helps, thanks a lot.
  
  **Tags:** reinforcement-learning, optimization, time-complexity, finite-markov-decision-process, interpolation
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2020-06-23. Score: 0
  
  Discretizing state/action space will always be a very expensive strategy, in fact I don't think you can do better than exponential time in state/action dimension that way.
  
  Now, you still haven't really explained your algorithm with the discretized states and actions. Given your known models, it sounds like you're planning on doing dynamic programming. This would definitely be an exponential time algorithm. You also haven't explained how you'd use your knowledge of the model in your policy gradient implementation. If you're just using it to sample some trajectories to have more data for updates, policy gradient methods will be much more efficient (poly-time). Otherwise, if you're planning on using your model for some sort of MCTS planning, depending on how you implement that, it could be very inefficient as well.
  
  > **Comments:**
  > **username_0**: Thank you for the respond, I agree if I discretize the state space it will be exponential time. And what's really costly is the optimization part, since I do not really know the shape of the function.  So I have to choose my optimizer carefully.  
  > **username_0**: And indeed, my knowledge of the model is used to simulate the some trajectories in order to update my policy.  
  
  ---
  
  