2022 Developer Survey is open! Take survey.
21 votes
Accepted

What is the difference between First-Visit Monte-Carlo and Every-Visit Monte-Carlo Policy Evaluation?

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 ...
user avatar
  • 33k
15 votes
Accepted

How does "Monte-Carlo search" work?

Monte Carlo method is an approach where you generate a large number of random values or simulations and form some sort of conlusions based on the general patterns, such as the means and variances. As ...
user avatar
7 votes

Why do we need importance sampling?

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 ...
user avatar
6 votes
Accepted

What does the term $|\mathcal{A}(s)|$ mean in the $\epsilon$-greedy policy?

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 ...
user avatar
  • 23.2k
6 votes
Accepted

Why does TD Learning require Markovian domains?

The Markov assumption is used when deriving the Bellman equation for state values: $$v(s) = \sum_a \pi(a|s)\sum_{r,s'} p(r,s'|s,a)(r + \gamma v(s'))$$ One requirement for this equation to hold is that ...
user avatar
  • 23.2k
5 votes

How do temporal-difference and Monte Carlo methods work, if they do not have access to model?

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 ...
user avatar
  • 202
5 votes
Accepted

What is the typical AI approach for solving blackjack?

Blackjack is usually modelled using Monte Carlo (MC) Methods. There is a lot of literature on MC methods which is interesting on its own right but here is a paper describing how MC is applied to ...
user avatar
5 votes

Why is the target called "target" in Monte Carlo and TD learning if it is not the true target?

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 ...
user avatar
4 votes
Accepted

Why is GLIE Monte-Carlo control an on-policy control?

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 ...
user avatar
4 votes
Accepted

Into which subcategories can reinforcement learning be divided?

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 ...
user avatar
  • 961
4 votes
Accepted

In MCTS, what to do if I do not want to simulate till the end of the game?

Famous example is AlphaZero. It doesn't do unrolls, but consults the value network for leaf node evaluation. The paper has the details on how the update is performed afterwards: The leaf $s'$ ...
user avatar
  • 1,773
4 votes
Accepted

Action-value estimation of deterministic policies with Monte Carlo method

But, in a real application under a given deterministic policy $\pi$, how can you choose the initial action $a$ arbitrarily at state $s$ because it is already fixed by the policy $\pi$: $a=\pi(s)$? ...
user avatar
  • 23.2k
3 votes

In what RL algorithm category is MiniMax?

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 ...
user avatar
  • 77
3 votes

How can we compute the ratio between the distributions if we don't know one of the distributions?

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 ...
user avatar
3 votes
Accepted

How can we compute the ratio between the distributions if we don't know one of the distributions?

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) $$ ...
user avatar
3 votes
Accepted

Do we need the transition probability function when calculating the importance sampling ratio?

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 ...
user avatar
  • 23.2k
3 votes
Accepted

In Monte Carlo learning, what do you do when an end state is reached, after having recorded the previously visited states and taken actions?

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 ...
user avatar
  • 23.2k
3 votes
Accepted

MCTS: How to choose the final action from the root

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" ...
user avatar
  • 9,326
3 votes
Accepted

What is the intuition behind TD($\lambda$)?

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 ...
user avatar
  • 33k
3 votes

What is the relation between Monte Carlo and model-free algorithms?

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 ...
user avatar
  • 23.2k
3 votes

Monte-Carlo, every-visit gridworld, exploring starts, python code gets stuck in foreverloop in episode generation

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 ...
user avatar
  • 23.2k
3 votes
Accepted

What is the bias-variance trade-off in reinforcement learning?

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 ...
user avatar
  • 961
3 votes
Accepted

Why are state-values alone not sufficient in determining a policy (without a model)?

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 ...
user avatar
  • 23.2k
3 votes
Accepted

Why does Monte Carlo policy evaluation relies on action-value function rather than state-value function?

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 ...
user avatar
  • 1,201
3 votes
Accepted

Is the expected value we sample in TD-learning action-value Q or state-value V?

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 ...
user avatar
  • 23.2k
3 votes

With Monte Carlo off-policy learning what do we correct by using importance sampling?

We estimate a value using sampling on whole episodes, and we take this values to construct the target policy. The crucial bit that you are missing is that there is no single value of $V(s)$ (or $Q(s,...
user avatar
  • 1,773
2 votes

Why is Monte Carlo used as the tree search algorithm for AlphaGo?

The paper that introduced AlphaGo, Mastering the game of Go with deep neural networks and tree search, motivates the use of MCTS Monte Carlo tree search (MCTS) uses Monte Carlo rollouts to estimate ...
user avatar
  • 33k
2 votes
Accepted

Why Monte Carlo epsilon-soft approach cannot compute $\max Q(s,a)$?

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 ...
user avatar
  • 23.2k
2 votes
Accepted

How is the incremental update rule derived from the weighted importance sampling in off-policy Monte Carlo control?

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} ...
user avatar
2 votes
Accepted

Understanding the W term in off policy monte carlo learning

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|...
user avatar
  • 23.2k

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