Content deleted Content added
Maxeto0910 (talk | contribs) |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (2 intermediate revisions by 2 users not shown) | |||
Line 13:
* <math>S</math> is a [[set (mathematics)|set]] of states called the ''<dfn>state space</dfn>''. The state space may be discrete or continuous, like the [[set of real numbers]].
* <math>A</math> is a set of actions called the ''<dfn>action space</dfn>'' (alternatively, <math>A_s</math> is the set of actions available from state <math>s</math>). As for state, this set may be discrete or continuous.
* <math>P_a(s, s')</math> is, on an intuitive level, the probability that action <math>a</math> in state <math>s</math> at time <math>t</math> will lead to state <math>s'</math> at time <math>t+1</math>. In general, this probability transition is defined to satisfy <math>\Pr(s_{t+1}\in S' \mid s_t = s, a_t=a)=\int_{S'} P_a(s, s')ds',</math> for every <math>S'\subseteq S</math> measurable. In case the state space is discrete, the integral is intended with respect to the [[counting measure]], so that the latter simplifies as <math>P_a(s, s')= \Pr(s_{t+1}=s' \mid s_t = s, a_t=a)</math>; In case <math>S\subseteq \mathbb R^d</math>, the integral is usually intended with respect to the [[Lebesgue measure]].
*<math>R_a(s, s')</math> is the immediate reward (or expected immediate reward) received after transitioning from state <math>s</math> to state <math>s'</math>, due to action <math>a</math>.
Line 26:
:<math>E\left[\sum^{\infty}_{t=0} {\gamma^t R_{a_t} (s_t, s_{t+1})}\right] </math> (where we choose <math>a_t = \pi(s_t)</math>, i.e. actions given by the policy). And the expectation is taken over <math>s_{t+1} \sim P_{a_t}(s_t,s_{t+1})</math>
where <math>\ \gamma \ </math> is the discount factor satisfying <math>0 \le\ \gamma\ \le\ 1</math>, which is usually close to <math>1</math> (for example, <math> \gamma = 1/(1+r) </math> for some discount rate <math>r</math>). A lower discount factor
Another possible, but strictly related, objective that is commonly used is the <math>H-</math>step return. This time, instead of using a discount factor <math>\ \gamma \ </math>, the agent is interested only in the first <math>H</math> steps of the process, with each reward having the same weight.
Line 40:
In many cases, it is difficult to represent the transition probability distributions, <math>P_a(s, s')</math>, explicitly. In such cases, a simulator can be used to model the MDP implicitly by providing samples from the transition distributions. One common form of implicit MDP model is an episodic environment simulator that can be started from an initial state and yields a subsequent state and reward every time it receives an action input. In this manner, trajectories of states, actions, and rewards, often called ''<dfn>episodes</dfn>'' may be produced.
Another form of simulator is a ''<dfn>generative model</dfn>'', a single step simulator that can generate samples of the next state and reward given any state and action.<ref name="Kearns Sparse">{{cite journal |last1=Kearns |first1=Michael |last2=Mansour |first2=Yishay |last3=Ng |first3=Andrew |title=A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes |journal=Machine Learning |date=2002 |volume=49 |issue=193–208 |pages=193–208 |doi=10.1023/A:1017932429737 |doi-access=free }}</ref> (Note that this is a different meaning from the term [[generative model]] in the context of [[statistical classification]].) In [[algorithms]] that are expressed using [[pseudocode]], <math>G</math> is often used to represent a generative model. For example, the expression <math>s', r \gets G(s, a)</math> might denote the action of sampling from the generative model where <math>s</math> and <math>a</math> are the current state and action, and <math>s'</math> and <math>r</math> are the new state and reward. Compared to an episodic simulator, a generative model has the advantage that it can yield data from any state, not only those encountered in a trajectory.
These model classes form a hierarchy of information content: an explicit model trivially yields a generative model through sampling from the distributions, and repeated application of a generative model yields an episodic simulator. In the opposite direction, it is only possible to learn approximate models through [[regression analysis|regression]]. The type of model available for a particular MDP plays a significant role in determining which solution algorithms are appropriate. For example, the [[dynamic programming]] algorithms described in the next section require an explicit model, and [[Monte Carlo tree search]] requires a generative model (or an episodic simulator that can be copied at any state), whereas most [[#Reinforcement learning|reinforcement learning]] algorithms require only an episodic simulator.
Line 109:
| access-date=November 2, 2023| hdl=1721.1/2893
| hdl-access=free
| url-access=subscription
}}</ref> However, due to the [[curse of dimensionality]], the size of the problem representation is often exponential in the number of state and action variables, limiting exact solution techniques to problems that have a compact representation. In practice, online planning techniques such as [[Monte Carlo tree search]] can find useful solutions in larger problems, and, in theory, it is possible to construct online planning algorithms that can find an arbitrarily near-optimal policy with no computational complexity dependence on the size of the state space.<ref>{{cite journal|last1=Kearns|first1=Michael|last2=Mansour|first2=Yishay|last3=Ng|first3=Andrew|date=November 2002|title=A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes|journal=Machine Learning|volume=49|issue=2/3 |pages=193–208 |doi=10.1023/A:1017932429737|doi-access=free}}</ref>
| |||