12

The first-visit and the every-visit Monte-Carlo (MC) algorithms are both used to solve the prediction problem (or, also called, "evaluation problem"), that is, the problem of estimating the value function associated with a given (as input to the algorithms) fixed (that is, it does not change during the execution of the algorithm) policy, denoted by $\pi$. In ...


6

This expression: $|\mathcal{A}(s)|$ means $|\quad|$ the size of $\mathcal{A}(s)$ the set of actions in state $s$ or more simply the number of actions allowed in the state. This makes sense in the given formula because $\frac{\epsilon}{|\mathcal{A}(s)|}$ is then the probability of taking each exploratory action in an $\epsilon$-greedy policy. The overall ...


6

The weights do sum to one. Note that in the second line where we have $$\frac{\epsilon}{|\mathcal{A}(s)|} \sum_a q_{\pi}(s,a) + (1-\epsilon)\max_aq_{\pi}(s,a) \; ,$$ the sum is over the whole action space, including the greedy action, so the sum of the weights will be $\frac{\epsilon}{|\mathcal{A}(s)|} \times |\mathcal{A}(s)| + (1-\epsilon) = 1$.


5

It is our "current" target. We assume that the value we get now is at least a closer approximation to the "true" target. We're not so much moving towards a wrong value as we are moving away from a more wrong value. Of course, it is all base on random trials, so saying anything definite (such as: "we are guaranteed to improve at each ...


4

The main idea is that you can estimate $V^\pi(s)$, the value of a state $s$ under a given policy $\pi$, even if you don't have a model of the environment, by visiting that state $s$ and following the policy $\pi$ after that state. If you repeat this process many times, you'll get many samples of trajectories starting at $s$ with some total return associated ...


4

In this case, $\pi$ has always been an $\epsilon$-greedy policy. In every iteration, this $\pi$ is used to generate ($\epsilon$-greedily) a trajectory from which the new $Q(s, a)$ values are calculated. The last line in the "pseudocode" tells you that the policy $\pi$ will be a new $\epsilon$-greedy policy in the next iteration. Since the policy ...


4

Your two suggestions are not mutually exclusive. If you go by this process, you'll have to do a "Cartesian product" of a bunch of different RL categorizations which would get out of hand. I recommend, if you can, to describe some sort of "RL taxonomy" instead. By this I mean describing different RL characterizations without assuming they'...


3

It is common in Bayesian statistics to only know the posterior up to a constant of proportionality. This means that we can't directly sample from the posterior. However, using importance sample we are able to. Consider our posterior density $\pi$ is only known up to some constant, i.e. $\pi(x) = K \tilde{\pi}(x)$, where $K$ is some constant and we only ...


3

The rationale behind importance sampling is that $q(x)$ is difficult to sample from but easy to evaluate. Or at least you can easily evaluate some $\tilde{q}$ such that: $$ \tilde{q}(z) = Zq(z) $$ where $Z$ (scalar) might be unknown. The geometrical example would be here e.g. sampling uniformly from an area under the curve $q(x)$ (in general it's not easy). ...


3

I think you are looking at it from the wrong direction, min-max is just a planning algorithm, decision strategy, in the sense that you are describing other algorithms/methods it does not have a category. For example, you have negamax algorithm which is in a sense the same thing the Monte Carlo Search Tree is to Monte Carlo. Min-max category is game theory ...


3

The technique used by AlphaGo is "Monte Carlo Tree Search", combined with a very well trained neural network. The network's job is to estimate the quality of different board states and moves. This estimation is deterministic. If you show AlphaGo the same board on two different occasions, it thinks it is exactly as good (or bad) on both occasions. Monte ...


3

There is one thing I don't particularly understand. Why do we need the state-transition probability function when calculating the importance sampling ratio for off-policy prediction? It is not needed for calculation. It must be included in the theory, to compare the correct probability of each trajectory (on-policy vs off-policy). However, the state ...


3

Your implementation of Monte Carlo Exploring Starts algorithm appears to be working as designed. This is a problem that can occur with some deterministic policies in the gridworld environment. It is possible for your policy improvement step to generate such a policy, and there is no recovery from this built into the algorithm. First visit and every visit ...


2

I am assuming you are asking about Monte Carlo simulation for value estimates, perhaps as part of a Monte Carlo control learning agent. The basic approach of all value-based methods is to estimate an expected return, often the action value $Q(s,a)$ which is a sum of expected future reward from taking action $a$ in state $s$. Monte Carlo methods take a direct ...


2

In the reinforcement learning is the value of terminal/goal state always zero? Yes, always for episodic problems, the value of a terminal state is always zero, from the definition. The value of a state $v(s)$ is the expected sum (perhaps discounted) of rewards from all future time steps. There are no future time steps when in a terminal state, so this sum ...


2

When using terms like "high" for high variance, this is in comparison to other methods, mainly in comparison to TD learning, which bootstraps between single time steps. It is worth spelling out what the variance applies to and where it comes from: Namely the Monte Carlo return $G_t$ distribution, which can be calculated as follows: $$G_t = \sum_{k=0}^{T-t-...


2

The left hand graphs are showing you the estimated value function from using Monte Carlo evaluation, after 10,000 episodes. They give a sense of what your value table will look like before convergence. In the case of upper "usable ace" chart, the estimates are still showing a lot of inaccuracy due to variance in the data. This is for two main reasons: The ...


2

The pseudocode you have copied looks incorrect to me, and I think it is from the first edition. The main issue is at the end of the loop. Where the book has $\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$ $\qquad \text{If } W = 0 \text{ then ExitForLoop}$ It should have either $\qquad W \leftarrow W \frac{1}{\mu(A_t|S_t)}$ $\qquad \text{If } \pi(S_t) \neq ...


2

By definition of $V_{n+1}$, we have: $V_{n+1} = \frac{\sum_{k=1}^{n} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{1}$ Then, taking the $n^{th}$ term out of the sum in the numerator, we have: $V_{n+1} = \frac{W_{n}G_{n} \; + \; \sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n} W_{k}} \; \tag{2}$ Then, from the definition of $V_n$, $V_{n} = \frac{\sum_{k=1}^{n-1} ...


2

The bias-variance trade-off that you're referring to has to do with the return estimator. Any RL algorithm you choose needs some estimate of the cumulative return, which is a random variable with many sources of randomness, such as stochastic transitions or rewards. Monte Carlo RL algorithms estimate returns by running full trajectories and literally ...


2

If $\pi$ is a random policy, and after running through this algorithm, and for each state take the $\max Q(s,a)$ for all possible actions, why would that not be equal to $Q_{\pi^*}(s, a)$ (optimal Q function)? Assuming that the estimates for $Q_{\pi}(s,a)$ have converged to close to correct values from many samples, then a policy based on $\pi'(s) = \text{...


2

By far the most commonly used strategy is to select the child with the highest number of visits. This is as described in the 2008 paper you linked. It's also what's referred to as the "robust child" in the 2012 paper you linked. In algorithm 2 of the 2012 paper, they actually use the highest average reward, which corresponds to "Max child". It looks like ...


2

In Reinforcement Learning (RL), the use of the term Monte Carlo has been slightly adjusted by convention to refer to only a few specific things. The more general use of "Monte Carlo" is for simulation methods that use random numbers to sample - often as a replacement for an otherwise difficult analysis or exhaustive search. In RL, Monte Carlo methods are ...


2

why is it not possible to suggest a policy solely on the basis of state-values; why do we need state-action values? A policy function takes state as an argument and returns an action $a = \pi(s)$, or it may return a probability distribution over actions $\mathbf{Pr}\{A_t=a|S_t=s \} =\pi(a|s)$. In order to do this rationally, an agent needs to use the ...


1

A full Bellman update can be intractable. For instance, if your state space or action space are continuous, the full Bellman update is intractable. You can try to solve this by discretizing, but if your state space is large this will also be intractable.


1

In step 2 I need to decide for an initial estimate $\tilde{Q}_n$. Is it a decent option to use $\tilde{Q}_n=Q_{n-1}$? Yes, this is a common choice. It's actually common to update the table for $\tilde{Q}$ in place, without any separate initialisation per step. The separate phases of estimation and policy improvement are easier to analyse for theoretical ...


1

each episode you will calculate the return, you will then update the action value or $Q(s,a)$ as the average each episode. Using the blackjack example from open AI gym and using a discount factor of 1, you get the following episode 1 [{'state': (22, 10, False), 'reward': -1, 'action': 1}, {'state': (17, 10, False), 'reward': 0, 'action': 1}, {'state': (...


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


1

TD($\lambda$) can be thought of as a combination of TD and MC learning, so as to avoid to choose one method or the other and to take advantage of both approaches. More precisely, TD($\lambda$) is temporal-difference learning with a $\lambda$-return, which is defined as an average of all $n$-step returns, for all $n$, where an $n$-step return is the target ...


1

I feel the general answer is that we want to be as efficient as possible in learning from experience. Policy improvement here always produces an equivalent or better policy, so delaying the improvement step to gather more episodes will only slow down learning. I would note too that often a different kind of Monte Carlo learning is used. Instead the speed ...


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