Tag Info

Hot answers tagged monte-carlo-methods

7

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 $$... 4 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' position is expanded and evaluated only once by the network to gene-rate both prior probabilities and evaluation, (P(s′ , \cdot),V(s ′ )) = f_\theta(s′ ). Each edge ... 3 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,a)) of a state (or a state action pair). These value functions are always defined with respect to some policy \pi(a|s) and is given the notation of V^{\pi}(... 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 ... 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, ... 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 ...

2

You are right that the strict equality $q_\pi(s,\pi(s)) = v_\pi(s)$ is generally true for a deterministic policy $\pi$. The $\geq$ inequality is also correct, of course, and it could be that the authors' intention was to show that $\pi_{k+1}$ and $\pi_k$ satisfy the condition for the policy improvement theorem: Let $\pi$ and $\pi'$ be any pair of ...

2

For every visit MC you create a list for each state. Every time you enter a state you calculate the returns for the episode and append these returns to a list. Once you have done this for all the episode you want to average over you simply calculate the value of a state to be the average of this list of returns for the state. First visit MC is almost the ...

2

So why is constant-$\alpha$ being used? This is because control scenarios are inherently non-stationary with respect to value functions. Decaying alpha comes with a risk that improvements to the policy will occur progressively more slowly, because the impact to changing the policy will be learned slowly. From my understanding, in stationary environments, ...

1

My question is if I should select state_action pairs by theirs immediate reward or should I select them by the episode reward? By the return (sum of all rewards) from the whole episode. A lot of decisions made in "good" episodes do not lead to immediate rewards, but instead transition towards states where better rewards are possible. In retrospect,...

1

I think that this is an intentional subtle detail of the algorithm that ensures the convergence property. The claim in the book is that for any $b$ that provides us with "an infinite number of returns for each pair of state and action" the target policy $\pi$ will converge to optimal. Imagine now that we have such a bad policy $b$ that it never ...

1

External sampling and outcome sampling are two ways of defining the sets $Q_1, \dots, Q_n$. I think your mistake is that you think of the $Q_i$ as fixed and taken as input in these shampling schemes. It is not the case. In external sampling, there is as many sets $Q_{\tau}$ as there are pure strategies for the opponent and the chance player (a pure strategy ...

1

Q1. When expanding the choices at the leaf node L, do I expand all, a few or just one child? Expanding all nodes or expanding just one node are both possible. There are different advantages and disadvantages. The obvious disadvantage of immediately expanding them all is that your memory usage will grow more quickly. I suppose that the primary advantage is ...

1

There are a few different ways to improve on your simple heuristic approach, but they mostly resolve to these three things: Find a better heuristic. This could be done by calculating probabilities of results, or running loads of training simulations and somehow tuning the heuristic function. Look-ahead search/planning. There are many possible search ...

1

I am a novice in Reinforcement Learning and I have been struggling for several monthes about the TD()'s logic. Initially it seemed to me that it was a successfull purely heuristic formula without any theoretical foundation. But nowadays, I understand it simply as a mean's calculation, using the recurrent formula that states that when you a have a mean and a ...

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