# Tag Info

## Hot answers tagged value-iteration

4

$\pi(s)$ does not mean $q(s,a)$ here. $\pi(s)$ is a policy that represents probability distribution over action space for a specific state. $q(s,a)$ is a state-action pair value function that tells us how much reward do we expect to get by taking action $a$ in state $s$ onwards. For the value iteration on the right side with this update formula: $v(s) \... 4 I'll start with the last question in your post: I was also wondering if there are any theoretical proofs/explanations about reward/Q-value clipping and which one being better. I highly doubt there will be any such theoretical work. The problem is that these variants of clipping (clipping rewards and clipping$Q$values) fundamentally modify the task / ... 4 TL;DR: It is Q learning. However Q learning is basically sample-based value iteration, so not surprising you see a similarity. Q learning* and value iteration are very strongly related. When considering action values, both approaches use the same Bellman equation for optimal policy,$q^*(s,a) = \sum_{r,s'}p(r,s'|s,a)(r+\gamma \text{max}_{a'} q^*(s', a'))$... 3 The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value using the optimal policy. According to the optimal policy, the agent would choose to stay in the square (1,1) every time, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of ... 3 I am wondering which definition is correct. The asterisk * in both the definitions stands for "optimal" in the sense of "value when following the optimal policy" So this one is correct: V* actually assumes the optimal action in a given state, meaning V* would be 50 in the above case However, you have got the definition of Q slightly wrong. I think ... 3 1): The intuition is based on the concept of value iteration, which the authors mention but don't explain on page 504. The basic idea is this: imagine you knew the value of starting in state x and executing an optimal policy for n timesteps, for every state x. If you wanted to know the optimal policy (and it's value) for running for n+1 timesteps in each ... 3 What you could do is to trigger environment termination when rat either: steps into the trap picks both cheese pieces The problem with such setup is that, when the rat picks a single piece, it would move one step to the side, and then it would come back to the same cheese spot so it would keep exploiting the same spot indefinitely. The solution to ... 3 I was able to solve the problem with the help of comment from @NeilSlater. The main issue for non-convergence was that I was not decaying the learning rate appropriately. I put a decay rate of$-0.00005$on the learning rate lr and subsequently Q-Learning also converged to the same value as value iteration. 2 Is it still a policy iteration algorithm if the policy is updated optimizing a function of the immediate reward instead of the value function? Technically yes. The value update step in Policy Iteration is: $$v(s) \leftarrow \sum_{r,s'}p(r,s'|s,\pi(s))(r + \gamma v(s'))$$ The discount factor$\gamma$can be set to$0$, making the update:$$v(s) \... 2 The reward function can be a function of the current state, current action, and next state:$R(s_t, a_t, s_{t+1})$. It's valid to use the Bellman operator in this setting because it's still a contraction and will yield the optimal value function. NOTE: I'm assuming that you will be solving the MDP with the Bellman equation. 2 A policy can be stochastic or deterministic. A deterministic policy is a function of the form$\pi_{\text{deterministic}}: S \rightarrow A$, that is, a function from the set of states to the set of actions. A stochastic policy is a map of the form$\pi_{\text{stochastic}} : S \rightarrow P(A)$, where$P(A)$is a set of probability distributions ($P(A) = \{ ...

2

Keeping this taxonomy intact for model-based Dynamic programming algorithms, I would argue that value iteration is a Actor only approach, and policy iteration is a Actor-Critic approach. However, not many people discuss the term Actor-Critic when referring to Policy Iteration. How come? Both policy iteration and value iteration are value-based approaches. ...

2

I will fill in some details in shaabhishek's answer for people who are interested. With this in mind, what is the value of a square (1,1)? First of all, the value function is dependent on a policy. The supposed correct answer you provided is the value of $(1, 1)$ under the optimal policy, so from now on, we will assume that we are finding the value ...

2

It seems to me that you're thinking about the parameters a and b as being characteristic of the agent that's moving in the environment (therefore determining the final policy), but they are actually a characteristic of the environment. Think of a frozen lake. You want to pass the lake but there is a hole five meters in front of you. Let's say you have boots ...

1

Nevermind. I found that above answer is indeed correct, but the gradescope has a bug (it requires the format to be .2 instead of 0.2).

1

In the standard policy iteration algorithm presented in Sutton and Barto's book, you alternate between a policy evaluation (PE) step and a policy improvement (PI) step (i.e. PE, PI, PE, PI, PE, PI, PE, ...). However, in general, you don't have to follow this alternation strictly in order to converge (in the limit) to the optimal policy. For example, value ...

1

Both value iteration (VI) and policy iteration (PI) algorithms are guaranteed to converge to the optimal policy, so it is expected that you get similar policies from both algorithms (if they have converged). However, they do this differently. VI can be seen as truncated version of PI. Let me first illustrate the pseudocode of both algorithms (taken from ...

1

First thing to know is that, in this case, values for the gridworld in new iteration are completely calculated with respect to the old values from the previous iteration. Value of $0.78$ is got like this: $0.9 \cdot (0.8 \cdot 1 + 0.1 \cdot 0.72 + 0.1 \cdot 0) = 0.7848 \approx 0.78$ term $0.8 \cdot 1$ is for going to the right with probability of $0.8$ ...

1

The update equation for value iteration that you show is time complexity $O(|\mathcal{S}\times\mathcal{A}|)$ for each update to a single $V(s)$ estimate, because it iterates over all actions to perform $\text{max}_a$ and over all next states for $\sum_{s'}$. The sources you have found are probably counting an entire sweep through the state space as an "...

Only top voted, non community-wiki answers of a minimum length are eligible