Questions tagged [dynamic-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
1
vote
1answer
23 views

Add maximum time step to value iteration algorithm

What would a value iteration algorithm look like if I specify a maximum time step? For example, from a given state the environment does not reach a terminating state but instead should terminate ...
0
votes
0answers
21 views

Circular reference in states of the Bellman equation

I want to formulate a game of darts as a dynamic program. The goal is to minimize the number of darts thrown while reaching checkout. A dart player has a score s. If his score is s = ...
0
votes
0answers
47 views

Bellman equation / dynamic programming for darts

When you play darts, you can throw at 62 regions, z on the dartboard. Namely, the singles regions S1, ..., S20, the double regions D1, ..., D20, the treble regions T2, ..., T20 and the single- and ...
1
vote
0answers
36 views

Bellman Optimality Operator fixed point

I'm reading Szepesvári's book on RL. My question is concerning the proof of Theorem A.10 (p. 71). Theorem Let $V$ be the fixed point of $T^∗$ and assume that there is policy $π$ which is greedy w.r.t ...
0
votes
0answers
28 views

How does AlphaZero guarantee it could make consistent improvement?

I know the detail of AlphaZero. And in detail, I know it is improving by "policy iteration" mechanism. I found an answer that prove it can finally converge to optimal. But... Is it still ...
0
votes
0answers
23 views

Bellman equations and reinforcement learning

We need to define just a few things first: $(a_t, s_t) \in \mathcal{A} \times \mathcal{S}$ are the action and state at time $t$; $r(s_t, a_t)$ is the reward for taking action $a_t$ in state $s_t$; ...
1
vote
2answers
597 views

Choosing a changepoint detection algorithm

I've been reading up on changepoint algorithms (dynamic programming, Bayesian Online Changepoint detection, Hidden Markov Models, etc.) and am looking to implement an algorithm that has a certain set ...
1
vote
1answer
66 views

Efficiency of Viterbi Algorithm

Considering that we have a sequence of observed states $\{y_1, y_2, \dots, y_T \}$ of length $T$. We want to generate a path $\{x_1, x_2, \dots, x_T\}$, which is a sequence of states $x_n \in S = \{...
2
votes
1answer
221 views

Value of the absorbing state in a MDP and greedy policy - Why choose to go to the absorbing state if state value is 0?

I was going through an example of a Markov Decision Problem and I got the optimal value function with the value iteration algorithm described in Sutton Barto. In this algorithm I chose to initialise ...
0
votes
1answer
224 views

calculate a quarterly average, a monthly data [closed]

I'm new to R, maybe this is very simple but I don't know how to do it I have the following data ...
2
votes
1answer
4k views

Dyna-Q Algorithm Reinforcement Learning

In step(f) of the Dyna-Q algorithm we plan by taking random samples from the experience/model for some steps. Wouldn't it be more efficient if we construct an MDP from experience by computing the ...
0
votes
1answer
85 views

Unique game problem (ML, DP, PP etc) [closed]

Looking for a solution to my below game problem. I believe it to be some sort of dynamic programming, machine learning, or probabilistic programming challenge, but am unsure... This is my original ...
2
votes
0answers
56 views

Understanding Approximate Dynamic Programming

I am trying to write a paper for my optimization class about Approximate Dynamic Programming. I found a few good papers but they all seem to dive straight into the material without talking about the ...
7
votes
0answers
2k views

Why are the value and policy iteration dynamic programming algorithms?

Algorithms like policy iteration and value iteration are often classified as dynamic programming methods that try to solve the Bellman optimality equations. My current understanding of dynamic ...