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
10
votes
3answers
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 ...
5
votes
1answer
86 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 ...
4
votes
1answer
239 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 ...
3
votes
1answer
53 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 ...
3
votes
1answer
53 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 ...
2
votes
2answers
63 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 ...
2
votes
1answer
135 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 ...
2
votes
1answer
53 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?
2
votes
0answers
49 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. ...
1
vote
1answer
37 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. ...
1
vote
1answer
38 views

Bellman optimality equation - writing the expression in 2 ways

Okay, I know this question is very basic but I saw two versions of the optimaltiy equation for $V_{*}(s)$ (and probably $Q_{*}(s,a)$). The first one is: and the second one is : If following ...
1
vote
1answer
26 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)?
1
vote
1answer
128 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 ...
1
vote
1answer
41 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 ...
1
vote
1answer
48 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? ...
1
vote
0answers
219 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 ...
0
votes
1answer
99 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) ...
0
votes
0answers
25 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 ...
0
votes
0answers
28 views

How DynaQ behaves in stochastic world in comparison with other reinforcement learning algorithms?

I came across of implementations of a bunch of algorithms on stochastic windy gridworld. This is the graph comparing their performance: So clearly, it seems that DynaQ performs better than all other ...