# Tag Info

6

First of all, efficiency and convergence are two different things. There's also the rate of convergence, so an algorithm may converge faster than another, so, in this sense, it may be more efficient. I will focus on the proof that policy evaluation (PE) converges. If you want to know about its efficiency, maybe ask another question, but the proof below also ...

4

Yes, the two update equations are equivalent. As an aside, technically the equation you give is not the Bellman equation, but the update step re-written as an equation - in the Bellman equation instead of $v_{k+1}(s)$ or $v_{k}(s)$ (showing iterations of approximate value functions), you would have $v_{\pi}(s)$ (representing the true value of a state under ...

3

In essence, your question is about convergence of infinite series. The mathematical discipline that studies such series is hundreds (if not thousands) years old an has nothing to do with "hardware architecture". A basic example of an infinite series is the geometric series: $$S = 1 + \gamma + \gamma^2 + \gamma^3 + \dots$$ Note that the series is ...

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

Why are we allowed to convert the Bellman equations into update rules? There is a simple reason for this: convergence. The same chapter 4 of the same book mentions it. For example, in the case of policy evaluation, the produced sequence of estimates $\{v_k\}$ is guaranteed to converge to $v_\pi$ as $k$ (i.e. the number of iterations) goes to infinity. There ...

2

The issue is that in your list comprehension in def V_pi(state) you have return sum(prob * (reward + mdp.discount*V[newState]) for prob, reward, newState in mdp.succProbReward(state)) whereas with the way you have defined the succProbReward output, it should be return sum(prob * (reward + mdp.discount*V[newState]) for newState, prob, reward in ...

2

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 $... 1 For off-policy learning you must have two policies - a behaviour policy and a target policy. If the two policies are the same, then you end up with SARSA, not Q learning. You cannot use Q learning directly for evaluating a fixed target policy, because it directly learns optimal value function as the target policy, regardless of the behaviour policy. Instead ... 1 The renowned book Reinforcement Learning: An Introduction (2nd edition), by Sutton and Barto, provides a different update rule than your first update rule for policy evaluation. Their update rule is more similar to your second update rule. See section 4.1. They also provide the pseudocode for policy evaluation on page 75 of the book. You can also find the ... 1 How does policy evaluation work for continuous state space model-free approaches? ... Let's say you use a DQN to find another policy, how does model-free policy evaluation work then? Policy evaluation is the process of determining state-value$v_{\pi}(s)$or action-value$q_{\pi}(s, a)\$ functions for the current policy. In the context of continuous state ...

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