Questions tagged [monte-carlo-methods]

For questions related to the Monte Carlo methods in reinforcement learning and other AI sub-fields. ("Monte Carlo" refers to random sampling of the search space.)

Filter by
Sorted by
Tagged with
1 vote
1 answer
20 views

Understanding the policy improvement theorem for Monte Carlo Control without Exploring Starts

I am currently studying the equations 5.2 in Reinforcement Learning An Introduction By Sutton and Barto on page 101. I want to comprehent the proof by a simple example: Having only one State with two ...
bake_thi's user avatar
2 votes
1 answer
31 views

Why is there the potential problem of "learning only from the tails of episodes" in off-policy MC control?

Sutton-Barto page 111, first paragraph (Off-policy Monte Carlo Control): A potential problem is that this method learns only from the tails of episodes, when all of the remaining actions in the ...
DSPinfinity's user avatar
1 vote
1 answer
162 views

Confused about Monte Carlo first visit algorithm

I'm really confused about understanding the Monte Carlo first visit algorithm as presented in the Sutton & Barto's book in chapter V. Here is the pseudocode: The reason is that I'm trying to ...
Dave's user avatar
  • 155
0 votes
0 answers
53 views

Finding a value at which TD(lambda) and Monte Carlo Are Similar

Let's say that I'm trying to find a value of lambda for which running a TD(lambda) method will produce the same results as a Monte Carlo method (within a small margin or error, of course). One of the ...
faangorn's user avatar
3 votes
1 answer
165 views

How does Monte-Carlo Tree Search Compare to MCMC?

Monte-Carlo Tree Search was the method used for AlphaGo my understanding is: it would randomly search the state space of possible moves where the probability of choosing a move was proportional to the ...
profPlum's user avatar
  • 424
2 votes
1 answer
232 views

How does off-policy Monte Carlo weighted importance sampling bias converge to zero (Sutton & Barto Section 5.5)

On Section 5.5 (page 105) of Sutton & Barto's "Reinforcement Learning: An Introduction", they discuss the off-policy Monte Carlo method for learning the value function of a target policy ...
user118967's user avatar
1 vote
1 answer
224 views

In off-policy MC learning, why is the probability of sampling a trajectory the same as having a return?

In Sutton and Barto's RL book, in the section for off-policy learning, we would like to find the expected value of the random variable $G_t$, given $S_t = s$ under our target policy: $$\mathbb{E}_{\pi}...
ArminAshrafi's user avatar
3 votes
0 answers
60 views

How does off-policy monte carlo explore and converge? [duplicate]

Premises to question: Behavior Policy: e-greedy (stochastic) Target Policy: greedy (deterministic) Importance Sampling Included In off-policy Monte-Carlo control, the behavior policy chooses actions ...
Jonah Kim's user avatar
2 votes
1 answer
58 views

Comparing Reinforcement Learning models

I am currently completing my thesis on optimising combinatorial problems, and we decided to utilize reinforcement learning. The problem is that I am not sure which algorithm to choose. Is there a ...
Rami Hoteit's user avatar
1 vote
2 answers
64 views

Given a set of trajectories produced by a fixed policy, what is the the standard approach to estimate Q?

Let's say that I have a set of trajectories $\mathcal{D} = \{\tau_1, \dots, \tau_n\}$ produced by an agent acting in a (episodic) MDP with a fixed policy $\pi$. I would like to estimate the $Q$ ...
Onil90's user avatar
  • 183
0 votes
1 answer
212 views

Action-value estimation of deterministic policies with Monte Carlo method

In Monte Carlo-based action value estimation problem for a deterministic policy (estimation of $q_{\pi}(s,a)$),the estimation problem seems not to be well-defined because $q_{\pi}(s,a)$ by ...
user3489173's user avatar
2 votes
1 answer
612 views

How to code an $\epsilon$-soft policy for on-policy Monte Carlo control?

I was trying to code the on-policy Monte Carlo control method. The initial policy chosen needs to be an $\epsilon$-soft policy. Can someone tell me how to code an $\epsilon$-soft policy? I know how to ...
A Q's user avatar
  • 23
2 votes
1 answer
326 views

How does the learning rate $\alpha$ vary in stationary and non-stationary environments?

In Sutton and Barto's book (Chapter 6: TD learning, 2nd edition), he mentions two ways of updating value function: Monte Carlo method: $V(S_t) \leftarrow V(S_t) + \alpha[G_t - V(S_t)]$. TD(0) method: ...
user529295's user avatar
1 vote
1 answer
88 views

In the cross-entropy method, should I select state-action pairs by their immediate reward or by the episode reward?

I am trying to understand the code mechanics when selecting the elite states and elite actions. It appears clear to me that they are those that appear in the episodes with the rewards bigger than the ...
Hermes Morales's user avatar
2 votes
0 answers
104 views

Doubt in Sutton & Barto's off-policy Monte Carlo control algorithm

The algorithm is described as below: My understanding: In the third last step, we act greedily w.r.t $Q$. Since we use importance sampling, this $Q \approx Q_\pi$. However, in the next step, whenever ...
user529295's user avatar
1 vote
0 answers
82 views

What is the sample complexity of Monte Carlo Exploring Starts in RL?

We can use a model-free Monte Carlo approach to solving an MDP $(S,A,R,P,\gamma)$ with transition dynamics $P$ unknown by estimating Q-values by rolling out trajectories starting from random states $...
Snowball's user avatar
  • 225
0 votes
1 answer
155 views

GLIE MC control (reinforcement learning): how the policy affects evaluation?

In his lecture 5 of the course "Reinforcement Learning", David Silver introduced GLIE Monte-Carlo Control. I understand that we do policy evaluation for one step and then policy improvement....
alwayscurious's user avatar
2 votes
1 answer
248 views

In off-policy MC control algorithm by Sutton & Barto, why do we perform a last update when sample action is inconsistent with target policy?

I have a question about the $W$ term in the off-policy MC control algorithm on Page 111 of Sutton & Barto. I have also included it in the figure below. My question: shouldn't the check $A_{t} = \...
Curious2learn's user avatar
1 vote
1 answer
90 views

When showing that the policy improvement theorem applies to MC control, why is $q_{\pi_{k}}\left(s, \pi_{k}(s)\right) \geq v_{\pi_{k}}(s)$ true?

When discussing why the policy improvement theorem is true, when we do Monte Carlo control by updating greedily, it says on page 98 of Sutton and Barto's book (2nd edition) that: $$ \begin{aligned} ...
Snowball's user avatar
  • 225
0 votes
0 answers
219 views

Comparison between TD(0) and MC ( or GAE )?

I'm getting started with DRL and have trouble distinguishing TD(0), MC, and GAE; and which scenarios one's better than others. Here is what I understand so far: TD(0): increment learning, can learn ...
Ngoc Bui's user avatar
2 votes
2 answers
310 views

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

I do not understand the link of importance sampling to Monte Carlo off-policy learning. We estimate a value using sampling on whole episodes, and we take these values to construct the target policy. ...
Hermes Morales's user avatar
5 votes
1 answer
552 views

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

I'm trying to implement MCTS with UCT for a board game and I'm kinda stuck. The state space is quite large (3e15), and I'd like to compute a good move in less than 2 seconds. I already have MCTS ...
Sami's user avatar
  • 53
1 vote
1 answer
980 views

How exactly is Monte Carlo counterfactual regret minimization with external sampling implemented?

I have read many papers, such as this or this, explaining how external sampling works, but I still don't understand how the algorithm works. I understand you divide $Q$, which is the set of all ...
kpopgirl's user avatar
0 votes
1 answer
350 views

What are the popular approaches to estimating the Q-function?

I need the q-value for my RL training, there are some approaches: Brute-force the action sequence (this won't work for long sequence) Use a classic algorithm to optimise and estimate (this ain't much ...
Dan D.'s user avatar
  • 1,283
3 votes
0 answers
472 views

How can I use Monte Carlo Dropout in a pre-trained CNN model?

In Monte Carlo Dropout (MCD), I know that I should enable dropout during training and testing, then get multiple predictions for the same input $x$ by performing multiple forward passes with $x$, then,...
lebebop's user avatar
  • 31
5 votes
1 answer
1k views

Why do we need importance sampling?

I was studying the off-policy policy improvement method. Then I encountered importance sampling. I completely understood the mathematics behind the calculation, but I am wondering what is the ...
Alireza Hosseini's user avatar
1 vote
1 answer
210 views

When updating the state-action value in the Monte Carlo method, is the return the same for each state-action pair?

Referring to this post, in the following formula to update the state-action value $$ Q(s,a) = Q(s,a) + \alpha (G − Q(s,a)),$$ is the value of $G$ (the return) the same for every state-action $(s,a)$ ...
Hermes Morales's user avatar
2 votes
1 answer
600 views

Unclear definition of a "leaf" and diverging UTC values in the Monte Carlo Tree Search

I have two questions regarding the Selection and Expansion steps in the Monte Carlo Tree Search Algorithm. In order to state the questions, I recall the algorithm that I believe is the one most ...
Marlo's user avatar
  • 123
0 votes
0 answers
470 views

Is my pseudocode titled "Monte Carlo Exploring Starts (with model)" correct?

Reinforcement Learning: An Introduction second edition, Richard S. Sutton and Andrew G. Barto: We made two unlikely assumptions above in order to easily obtain this guarantee of convergence for the ...
Дмитрий Винник's user avatar
0 votes
1 answer
125 views

When we have multiple traces, do we average over traces or the total number of times we have visited that state?

I am confused about the workings of the first- and every-visit MC. My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?...
InvestingScientist's user avatar
0 votes
0 answers
486 views

Suppose every-visit MC was used instead of first-visit MC on blackjack. Would you expect the results to be different?

This is a question from page 94 of Sutton and Barto's RL book 2020. I read in someone's compiled GitHub answers to this book's exercises their answer was: "No because each state in an episode of ...
user8714896's user avatar
3 votes
1 answer
211 views

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

Both MC and TD are model-free and they both follow a sample trajectory (in the case of TD, the trajectory is cut-short) to estimate the return (we basically are sampling Q values). Other than that, ...
Aung Khant's user avatar
1 vote
1 answer
443 views

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

Here is David Silver's lecture on that. Look at 9:30 to 10:30. He says that, since it is model-free learning, the environment's dynamics are unknown, so the action-value function $Q$ is used. But ...
Aung Khant's user avatar
4 votes
2 answers
314 views

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

I was going through Sutton's book and, using sample-based learning for estimating the expectations, we have this formula $$ \text{new estimate} = \text{old estimate} + \alpha(\text{target} - \text{old ...
Chukwudi Ogbonna's user avatar
5 votes
1 answer
509 views

Why does TD Learning require Markovian domains?

One of my friends and I were discussing the differences between Dynamic Programming, Monte-Carlo, and Temporal Difference (TD) Learning as policy evaluation methods - and we agreed on the fact that ...
stoic-santiago's user avatar
4 votes
1 answer
453 views

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

"If a model is not available, then it is particularly useful to estimate action values (the values of state-action pairs) rather than state values. With a model, state values alone are sufficient ...
stoic-santiago's user avatar
4 votes
1 answer
155 views

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

I've been looking online for a while for a source that explains these computations but I can't find anywhere what does the $|A(s)|$ mean. I guess $A$ is the action set but I'm not sure about that ...
Metrician's user avatar
1 vote
0 answers
181 views

Monte Carlo Exploring Starts broke for 2048 game AI

I implemented a MCES for 2048 (the game), with a quality function implemented as a neural net of a single layer. The starts are created with 6 cells filled with values between 64 and 1024, two cells ...
EmmanuelMess's user avatar
1 vote
1 answer
49 views

If the transition model is available, why would we use sample-based algorithms?

Sample-based algorithms, like Monte Carlo Algorithms and TD-Learning, are often presented as useful since they do not require a transition model. Assuming I do have access to a transition model, are ...
chessprogrammer's user avatar
1 vote
0 answers
83 views

Should the importance sampling ratio be updated at the end of the for loop in the off-policy Monte Carlo control algorithm?

I'm studying RL with Sutton and Barto's book. I'd like to ask about the order of execution of a statement in the algorithm below. Here, $W$ (importance sampling ratio) is updated at the end of the <...
JungYT's user avatar
  • 11
2 votes
1 answer
112 views

Into which subcategories can reinforcement learning be divided?

In the course of a scientific work, I will discuss the different types of reinforcement learning. However, I have difficulties to find these different types. So, into which subcategories can ...
jackless's user avatar
1 vote
0 answers
109 views

Why do bootstrapping methods produce nonstationary targets more than non-bootstrapping methods?

The following quote is taken from the beginning of the chapter on "Approximate Solution Methods" (p. 198) in "Reinforcement Learning" by Sutton & Barto (2018): reinforcement ...
Johan's user avatar
  • 121
2 votes
1 answer
2k views

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

I am watching DeepMind's video lecture series on reinforcement learning, and when I was watching the video of model-free RL, the instructor said the Monte Carlo methods have less bias than temporal-...
Aman Savaria's user avatar
5 votes
2 answers
599 views

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

Here is my understanding of importance sampling. If we have two distributions $p(x)$ and $q(x)$, where we have a way of sampling from $p(x)$ but not from $q(x)$, but we want to compute the expectation ...
pecey's user avatar
  • 333
3 votes
1 answer
503 views

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

Here's the approximated value using weighted importance sampling $$ V_{n} \doteq \frac{\sum_{k=1}^{n-1} W_{k} G_{k}}{\sum_{k=1}^{n-1} W_{k}}, \quad n \geq 2 $$ Here's the incremental update rule for ...
ExplorationExploitation's user avatar
3 votes
1 answer
1k views

In what RL algorithm category is MiniMax?

Q-learning is a temporal-difference method and Monte Carlo tree search is a Monte Carlo method. In what category is MiniMax?
mason7663's user avatar
  • 613
3 votes
0 answers
48 views

Why do we update $W$ with $\frac{1}{\mu (A_t | S_t)}$ instead of $\frac{\pi (A_t | S_t)}{\mu (A_t | S_t)}$ in off-policy Monte Carlo control?

I had the same question when I am reading the RL textbook from Sutton Bartol as posted here. Why do we update $W$ with $\frac{1}{\mu (A_t | S_t)}$ instead of $\frac{\pi (A_t | S_t)}{\mu (A_t | S_t)}$?...
roy's user avatar
  • 53
1 vote
0 answers
132 views

When does Monte Carlo linear function approximation converge?

In this Stanford lecture (minute 35:47 and 37:00), the professor says that Monte Carlo (MC) linear function approximation does not always converge, and she gives an example. In general, when does MC ...
dato nefaridze's user avatar
1 vote
1 answer
425 views

Monte Carlo epsilon-greedy Policy Iteration: monotonic improvement for all cases or for the expected value?

I was going through university slides and this particular slide is trying to prove that in a Monte Carlo Policy Iteration algorithm using an epsilon-greedy policy, the state Values (V-Values) are ...
devidduma's user avatar
  • 552
1 vote
1 answer
108 views

Understanding the W term in off policy monte carlo learning

In Sutton and Barto's RL textbook they included the following pseudocode for off policy Monte Carlo learning. I am a little confused, however, because to me it looks like the W term will become ...
Stephane Hatgis-Kessell's user avatar