14

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

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


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

Importance sampling is typically used when the distribution of interest is difficult to sample from - e.g. it could be computationally expensive to draw samples from the distribution - or when the distribution is only known up to a multiplicative constant, such as in Bayesian statistics where it is intractable to calculate the marginal likelihood; that is $$...


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


3

In Model Based Reinforcement learning, state and state-action values for all states can be calculated based on the bellman equations. The equations are taken from Andrew Ng's Algorithms for Inverse Reinforcement Learning $$V^{\pi}(s) = R(s) + \gamma \sum_{s'}P(s'|s,a)V^{\pi}(s') \\ Q^{\pi}(s,a) = R(s) + \gamma \sum_{s'}P(s'|s,a)V^{\pi}(s')$$ In this setting, ...


3

However, from the blogs and texts I read, the equations are expressed in terms of V and NOT Q. Why is that? MC and TD are methods for associating value estimates to time step based on experienced gained in later time steps. It does not matter what kind of value estimate is being associated across time, because all value functions are expressing the same ...


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

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

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

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


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

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

The discussion uses poor notation, there should be a time index. You obtain a list of tuples $(s_t, a_t, r_t, s_{t+1})$ and then, for every visit MC, you update $$Q(s_t, a_t) = Q(s_t, a_t) + \alpha (G_t - Q(s_t, a_t))\;;$$ where $G_t = \sum_{k=0}^\infty \gamma^k r_{t+k}$, for each $t$ in the episode. You can see that the returns for each time step are ...


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

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


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