Tag Info

4

I was able to solve the problem. 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.

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

Starting with rewards, states don't have rewards in general. A reward is a number returned at a certain step of the MDP. If you arrange things in sequence over a whole time step $s, a, r, s'$ for state, action, reward, next state, then the reward $r$ is allowed to depend on all three of $s, a, s'$, and it can also be from a random distribution of real ...

3

What is the difference between a reward and a value for a given state? Let us say that an agent took an action from state $A$ and reached state $B$ and got a score $R$. This instantaneous score the agent received on reaching state $B$ is called the reward. Now, let me introduce you to the concept of return. Assume that an agent followed a particular ...

3

Policy iteration is made up of two steps. The first is a full policy evaluation, where a value function is calculated for the current policy. The second is policy improvement, where the policy is made greedy with respect to the value function. Value iteration looks to speed things up by stopping policy evaluation after one iteration, make the policy greedy ...

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

There is a difference between accurate value function estimates, and optimal value functions. An optimal value function is more specifically the value function of an optimal policy. Value functions are always specific to some policy, which is why you will often see the subscript $\pi$ in e.g. $v_{\pi}(s)$ when there is a defined policy. The policy evaluation ...

3

So, naturally, if you've observed something that contradicts the theoretical properties of Value Iteration, something's wrong, right? Well, the code you've linked, as it is, is fine. It works as intended when all the values are initialized to zero. HOWEVER, my guess is that you're the one introducing an (admittedly very subtle) error. I think you're changing ...

3

You appear to comparing the value table update steps in policy iteration and value iteration, which are both derived from Bellman equations. Policy iteration In policy iteration, a policy lookup table is generated, which can be arbitrary. It usually maps a deterministic policy $\pi(s): \mathcal{S} \rightarrow \mathcal{A}$, but can also be of the form $\pi(a|... 3 Where the author mentions the policy evaluation being stopped after one state, they are referring to the part of the algorithm that evaluates the policy -- the pseudocode you have listed is the pseudocode for Value Iteration, which consists of iterating between policy evaluation and policy improvement. In normal policy evaluation, you would apply the update$...

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

For normal value iteration, you need to have the model, i.e. the transition probability, denoted by $P(s' \mid s,a)$. With Q-learning, you use the current reward and the already stored Q value: The relation between the value function $V(s)$ and the $Q$ function $Q(s, a)$ is that the $V(s)$ function is simply the value of the action $a$, such that $Q(s, a)$ ...

3

$\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) \... 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 ... 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

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 ...

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 ...

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

Is it possible to have values of the states equal to 0 at the end of the value iteration? Yes. For a start, all terminal states should have a value of zero. This is not usually learned or calculated, but is by definition because the value represents the sum of expected future rewards and a terminal state should not have any. However, if the terminal states ...

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

Policy and value iteration both require you to, for each possible transition and each corresponding possible reward at each state, compute a statistic of $r + \gamma V(s')$. In order for this to be tractable, you need for there to be at most finitely many states, actions, possible rewards, and possible transitions at each state. You also need to know the ...

1

What am I missing here? You are not missing anything mathematically. Potentially what you are missing is that the discount factor $\gamma$, is part of the problem definition. In reinforcement learning (RL), you do not always solve problems to obtain the highest total sum of rewards. Instead you solve problems to obtain the highest expected return on any ...

1

Policy iteration is based on the insight that for a given policy, it is straightforward to compute the value function (the long-run expected discounted value of being in a given stage) exactly -- it is a set of linear equations at that point. So, we update the policy, then calculate the exact values of the states for always following that particular policy, ...

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

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

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