Skip to main content

Questions tagged [dynamic-programming]

For questions related to the dynamic programming paradigm in the context of AI (and, in particular, reinforcement learning).

Filter by
Sorted by
Tagged with
2 votes
1 answer
226 views

Where does the TD formula for tic-tac-toe in Sutton & Barto come from?

In section $1.5$ of the book "Reinforcement Learning: An Introduction" by Sutton and Barto they use tic-tac-toe as an example of an RL use case. They provide the following temporal ...
mNugget's user avatar
  • 167
1 vote
1 answer
21 views

Why are there up to $m^2$ action values when we consider the complexity of DP based on $q(x,u)$?

Please see slide 32 in the following lecture slides on DP: https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf Let $m$ the size size of action ...
DSPinfinity's user avatar
1 vote
2 answers
34 views

Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?

Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem? I need a clear explanation.
DSPinfinity's user avatar
1 vote
0 answers
22 views

How to modify the bellman operator for in-place iterative policy evaluation?

The iterative update rule for policy evaluation that is, approximating the value function for a given policy is: $$v^{k+1} = r_{\pi} + \gamma P_{\pi}v^{k}$$ This is the simultaneous update rule where ...
Atharva's user avatar
  • 11
4 votes
2 answers
1k views

What is the relation between Dynamic Programming and Reinforcement Learning?

Please forgive me for the implicity of the question, as I recently started studying Reinforcement Learning. I am supposed to study a system where the transition probabilities are known and I have to ...
Annaassymeon2's user avatar
0 votes
0 answers
162 views

Clarification on Formulation of a DP Problem

I am self-teaching reinforcement learning and for now I am trying to solve the following DP problem: A driver is looking for inexpensive parking on the way to his destination. The parking area ...
ArGenya's user avatar
2 votes
0 answers
141 views

Why solely a one-step-lookahead in value/policy-iteration?

In value iteration and policy iteration we solely consider a one-step-lookahead where the lookahead is from the previous iteraiton and therefore need to sweep over all states and iterate this ...
hugh's user avatar
  • 53
0 votes
2 answers
97 views

How do we define greedy action for policy improvement for a given stochastic policy?

If we have a deterministic policy $\pi$ with action-value function $q(s,a)$, then a greedy action for policy improvement is defined as $\pi^\prime(s)=\arg\max_{a}q^{\pi}(s,a)$. How do we define a ...
DSPinfinity's user avatar
1 vote
1 answer
55 views

How is the Markov property of a general state-space model derived?

Below is the derivation for the Markov property of a general state-space model. The red part is not clear. Could someone please explain the steps in the sequential derivation for the red part?
DSPinfinity's user avatar
0 votes
1 answer
72 views

Consequence of Dvoretzky Stochastic Approximation Theorem

I am trying to understand all the steps to prove the TD0 algorithm, and I am following a proof which uses a theorem of Tommi Jaakkola, Michael I. Jordan and Satinder P. Singh, in the paper: On the ...
Kareit's user avatar
  • 19
1 vote
1 answer
348 views

Interpretation of the Dynamic Time Warping (DTW) graph

How can I interpret ate the DTW graph. I understood the algorithm behind DTW, but I struggle to interpret ate the graph. When I compute the DTW for a signal that is the same signal but shifted in time,...
Skobo Do's user avatar
1 vote
0 answers
36 views

Structured policies in dynamic programming: solving a toy example

I am trying to solve a dynamic programming toy example. Here is the prompt: imagine you arrive in a new city for $N$ days and every night need to pick a restaurant to get dinner at. The qualities of ...
learningowl's user avatar
1 vote
0 answers
143 views

Is there a way use DQN to find the optimal combination of actions (control inputs) and environment parameters?

I am using DQN to find the optimal sequence of control inputs to a dynamic system. The setup is as follows: At the beginning of each episode, the system is initialized to the SAME initial condition ...
David Braun's user avatar
0 votes
0 answers
34 views

Usefulness of the state_values calculation in Dynamic Programming

State values are always presented as a central concept in RL, notoriously in the bible, the Sutton&Barton’s book. I have done some exercises trying to improve my understanding, but it is clear ...
Hermes Morales's user avatar
1 vote
1 answer
251 views

How are these two versions of the Bellman optimality equation related?

I saw two versions of the optimality equation for $V_{*}(s)$ and $Q_{*}(s,a)$. The first one is: $$ V_{*}(s)=\max _{a} \sum_{s^{\prime}} P_{s s^{\prime}}^{a}\left(r(s, a)+\gamma V_{*}\left(s^{\prime}\...
Kronic's user avatar
  • 49
1 vote
1 answer
142 views

Is there a notion of exploration-exploitation tradeoff in dynamic programming (or model-based RL)?

Is there a notion of exploration-exploitation tradeoff in dynamic programming (or model-based RL)?
user529295's user avatar
1 vote
1 answer
56 views

How do we get from conditional expectation on both state and action to only state in the proof of the Policy Improvement Theorem?

I'm going through Sutton and Barto's book Reinforcement Learning: An Introduction and I'm trying to understand the proof of the Policy Improvement Theorem, presented at page 78 of the physical book. ...
Daviiid's user avatar
  • 575
3 votes
1 answer
195 views

Are policy and value iteration used only in grid world like scenarios?

I am trying to self learn reinforcement learning. At the moment I am focusing on policy and value iteration, and I am finding several problems and doubts. One of the main doubts is given by the fact ...
dcr's user avatar
  • 57
0 votes
1 answer
230 views

How do we get the value of this state of an MDP, at time-step $h-2$, using dynamic programming?

I am trying to understand the problem below, represented as an MDP with four states (PU, PF, RU, and RF) and two actions (AS). Let's consider V(RF), the value of the state RF. At time-step $h$, V(RF) ...
AHF's user avatar
  • 61
2 votes
0 answers
217 views

What trait of a planning problem makes reinforcement learning a well suited solution?

Planning problems have been the first problems studied at the dawn of AI (Shakey the robot). Graph search (e.g. A*) and planning (e.g. GraphPlan) algorithms can be very efficient at generating a plan. ...
50k4's user avatar
  • 225
1 vote
1 answer
84 views

Why is the update in-place faster than the out-of-place one in dynamic programming?

In Barto and Sutton's book, it's written that we have two types of updates in dynamic programming Update out-of-place Update in-place The update in-place is the faster one. Why is that the case? ...
VanasisB's user avatar
2 votes
1 answer
262 views

Is it possible to retrieve the optimal policy from the state value function?

One can easily retrieve the optimal policy from the action value function but how about obtaining it from the state value function?
Mika's user avatar
  • 341
1 vote
1 answer
288 views

Bellman optimality equation in semi Markov decision process

I wrote a Python program for a simple inventory control problem where decision epochs are equally divided (every morning) and there is no lead time for orders (the time between submitting an order ...
mnbobo's user avatar
  • 13
5 votes
1 answer
509 views

Why does TD Learning require Markovian domains?

One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that ...
stoic-santiago's user avatar
1 vote
1 answer
49 views

If the transition model is available, why would we use sample-based algorithms?

Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model. Assuming I do have access to a transition model, are ...
chessprogrammer's user avatar
4 votes
1 answer
599 views

Why is update rule of the value function different in policy evaluation and policy iteration?

In the textbook "Reinforcement Learning: An Introduction", by Richard Sutton and Andrew Barto, the pseudo code for Policy Evaluation is given as follows: The update equation for $V(s)$ comes from the ...
Jarvis1997's user avatar
1 vote
0 answers
425 views

How does the automated temperature adjustment step work in Soft Actor-Critic?

In section 5 of the paper Soft Actor-Critic Algorithms and Applications, it is proposed an optimization problem to obtain an optimal temperature parameter $\alpha^*_t$. First, one uses the original ...
Diego Gomez's user avatar
11 votes
3 answers
1k views

What algorithms are considered reinforcement learning algorithms?

What are the areas/algorithms that belong to reinforcement learning? TD(0), Q-Learning and SARSA are all temporal-difference algorithms, which belong to the reinforcement learning area, but is there ...
Miguel Saraiva's user avatar
3 votes
1 answer
238 views

What are the common techniques one could use to deal with collisions in a transposition table?

Consider an iterative deepening search using a transposition table. Whenever the transposition table is full, what are common strategies applied to replace entries in the table? I'm aware of two ...
ihavenoidea's user avatar
2 votes
1 answer
315 views

Do we need the transition probability function when calculating the importance sampling ratio?

I am reading the book titled "Reinforcement Learning: An Introduction" (by Sutton and Barto). I am at chapter 5, which is about Monte Carlo methods, but now I am quite confused. There is one thing I ...
Manuel Pasieka's user avatar
2 votes
2 answers
74 views

Should we feed a greater fraction of terminal states to the value network so that their values are learned first?

The basis of Q-learning is recursive (similar to dynamic programming), where only the absolute value of the terminal state is known. Shouldn't it make sense to feed the model a greater proportion of ...
Tejas Ramdas's user avatar