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
2
votes
2answers
130 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. ...
5
votes
1answer
54 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 ...
0
votes
0answers
31 views

Are regret values in each block of MC external sampling stored in each node of the block we are traversing down (denoted by $\{Q_1,…, Q_n\}$)?

Everything I know about Monte Carlo counterfactual regret minimization (CFR) comes from the paper Monte Carlo Sampling for Regret Minimization in Extensive Games by Marc Lanctot et al. So, I will use ...
1
vote
1answer
71 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 ...
0
votes
1answer
56 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 ...
2
votes
0answers
47 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,...
5
votes
1answer
123 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 ...
1
vote
1answer
55 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)$ ...
1
vote
1answer
37 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 ...
0
votes
0answers
60 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 ...
0
votes
1answer
42 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?...
0
votes
0answers
21 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 ...
3
votes
1answer
104 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, ...
1
vote
1answer
99 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 ...
1
vote
1answer
61 views

AI to play a solo card game

I would like to create an AI for the 1 player version of the card game called "The Game" by Steffen Benndorf (rules here: https://nsv.de/wp-content/uploads/2018/05/the-game-english.pdf). The ...
0
votes
0answers
44 views

How to prove variance infinite of monte carlo ordinary importance sampling estimator

In example 5.5 of Sutton and Barto's book for proving infinite variance of first visit monte carlo ordinary importance sampling estimator, $\mathbb{E}[(\Pi_t\frac{\pi(A_t|S_t)}{b(A_t|S_t)}G_0)^2]$ is ...
3
votes
2answers
192 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 ...
1
vote
1answer
72 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 ...
4
votes
1answer
82 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 ...
1
vote
0answers
89 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 ...
1
vote
1answer
39 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 ...
1
vote
0answers
24 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 <...
2
votes
1answer
86 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 ...
1
vote
0answers
29 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 ...
2
votes
1answer
221 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-...
6
votes
1answer
177 views

Is this proof of $\epsilon$-greedy policy improvement correct?

The text book being referred to, in this question is "Reinforcement Learning: An introduction" by Richard Sutton and Andrew Barto (second edition, 2018). For your convenience, I have ...
5
votes
2answers
326 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 ...
3
votes
1answer
60 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 ...
2
votes
1answer
113 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?
3
votes
0answers
37 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)}$?...
1
vote
0answers
53 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 ...
1
vote
1answer
118 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 ...
1
vote
1answer
46 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 ...
2
votes
2answers
243 views

How does Monte Carlo Exploring Starts work?

I'm having trouble understanding the 5th step in the flowchart. For the 5th step, the 'update the Q function by taking the average of returns' is confusing. From what I understand, the Q function ...
1
vote
1answer
72 views

MCTS moves with multiple parents

I'd like to develop an MCTS-like (Monte Carlo Tree Search) algorithm for program induction, i.e. learning programs from examples. My initial plan is for nodes to represent programs and for the search ...
2
votes
1answer
148 views

How to apply hyperparameter optimization on Monte Carlo Tree Search?

I have a basic MCTS agent for the game of Hex (a turn based game). I want to tune the parameters of UCT (the Cp parameter) and the number of rollouts parameter. Where do I have to begin? The problem ...
4
votes
1answer
69 views

How does policy evaluation work for continuous state space model-free approaches?

How does policy evaluation work for continuous state space model-free approaches? Theoretically, a model-based approach for the discrete state and action space can be computed via dynamic programming ...
1
vote
0answers
33 views

In reinforcement learning what do we mean by a model? [duplicate]

I was going through the chapter "Monte Carlo Methods" from the book "Reinforcement Learning" by Sutton and Barto. The author says that when a model is not available then it is useful to estimate ...
3
votes
1answer
184 views

How does Monte Carlo have high variance?

I was going through David Silver's lecture on reinforcement learning (lecture 4). At 51:22 he says that Monte Carlo (MC) methods have high variance and zero bias. I understand the zero bias part. It ...
2
votes
1answer
101 views

What does the figure “Blackjack Value Function…” from Sutton represent?

I came across this graph in David Silver's youtube lecture and Sutton's book on reinforcement learning. Can anyone help me understand the graph? From the graph, for 10000 episodes what i see is ...
6
votes
2answers
518 views

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

I'd like to better understand temporal-difference learning. In particular, I'm wondering if it is prudent to think about TD($\lambda$) as a type of "truncated" Monte Carlo learning?
2
votes
0answers
39 views

Why is this Monte Carlo approach scalable for a growing number of states variables and action variables?

I am reading a research paper on the formulation of MDP problems to ICU treatment decision making: Treatment Recommendation in Critical Care: A Scalable and Interpretable Approach in Partially ...
3
votes
1answer
121 views

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

I am new to Reinforcement learning and am currently reading up on the estimation of Q $\pi(s, a)$ values using MC epsilon-soft approach and chanced upon this algorithm. The link to the algorithm is ...
6
votes
1answer
505 views

MCTS: How to choose the final action from the root

When the time allotted to Monte Carlo tree search runs out, what action should be chosen from the root? The original UCT paper (2006) says bestAction in their ...
1
vote
1answer
31 views

Can I use my previous estimate of the state-action values as initialisation in GLIE-Monte Carlo Control?

I am trying to implement a tabular-based GLIE Monte-Carlo learning algorithm. So I repeat n times: create observations using my previous policy $\pi_{n-1}(s)$ update my state-action values using ...
3
votes
1answer
213 views

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

When you train a model using Monte Carlo-based learning the state and action taken at each step is recorded, and then at some point an end state is reached and the agent receives some reward - what do ...
2
votes
0answers
43 views

How to show Monte Carlo methods converge to an estimate which minimizes mean squared error?

In chapter six of Sutton and Barto (p.128), they claim Monte Carlo methods converge to an estimate minimizing the mean squared error. How can this be shown formally? Bump
2
votes
1answer
223 views

How is Monte Carlo different from model-based methods?

I was going through an article where it is mentioned: The Monte-Carlo methods require only knowledge base (history/past experiences)—sample sequences of (states, actions and rewards) from the ...
1
vote
1answer
177 views

Why does GLIE+MC Control Algorithm use a single episode of Monte Carlo evaluation?

GLIE+MC control Algorithm: My question is why does this algorithm use only a single Monte Carlo episode (during PE step) to compute the $Q(s,a)$? In my understanding this has the following drawbacks: ...
2
votes
2answers
107 views

How to stop evaluation phase in reinforcement learning with epsilon-greedy Monte Carlo agent?

I have implemented an epsilon-greedy Monte Carlo reinforcement learning agent like suggested in Sutton and Barto's RL book (page 101). As far as I understood epsilon-greedy agents so far, the ...