Марковтық шешім процесі: Математикалық модельдеу

Mathematical model
In mathematics, a Markov decision process (MDP) is a discrete time stochastic control process. It provides a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision maker. MDPs are useful for studying optimization problems solved via dynamic programming. MDPs were known at least as early as the 1950s; a core body of research on Markov decision processes resulted from Ronald Howard's 1960 book, Dynamic Programming and Markov Processes. They are used in many disciplines, including robotics, automatic control, economics and manufacturing. The name of MDPs comes from the Russian mathematician Andrey Markov as they are an extension of Markov chains. At each time step, the process is in some state , and the decision maker may choose any action that is available in state The process responds at the next time step by randomly moving into a new state , and giving the decision maker a corresponding reward
The probability that the process moves into its new state is influenced by the chosen action. Specifically, it is given by the state transition function Thus, the next state depends on the current state and the decision maker's action But given and , it is conditionally independent of all previous states and actions; in other words, the state transitions of an MDP satisfy the Markov property. Markov decision processes are an extension of Markov chains; the difference is the addition of actions (allowing choice) and rewards (giving motivation). Conversely, if only one action exists for each state (e. g. "wait") and all rewards are the same (e. g. "zero"), a Markov decision process reduces to a Markov chain.

In many cases, it is difficult to represent the transition probability distributions, , 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 episodes may be produced. Another form of simulator is a generative model, a single step simulator that can generate samples of the next state and reward given any state and action. (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, is often used to represent a generative model. For example, the expression might denote the action of sampling from the generative model where and are the current state and action, and and 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. 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 algorithms require only an episodic simulator.

Solutions for MDPs with finite state and action spaces may be found through a variety of methods such as dynamic programming. The algorithms in this section apply to MDPs with finite state and action spaces and explicitly given transition probabilities and reward functions, but the basic concepts may be extended to handle other problem classes, for example using function approximation. The standard family of algorithms to calculate optimal policies for finite state and action MDPs requires storage for two arrays indexed by state: value , which contains real values, and policy , which contains actions. At the end of the algorithm, will contain the solution and will contain the discounted sum of the rewards to be earned (on average) by following that solution from state
The algorithm has two steps, (1) a value update and (2) a policy update, which are repeated in some order for all the states until no further changes take place. Both recursively update a new estimation of the optimal policy and state value using an older estimation of those values. Their order depends on the variant of the algorithm; one can also do them for all states at once or state by state, and more often to some states than others. As long as no state is permanently excluded from either of the steps, the algorithm will eventually arrive at the correct solution.

In policy iteration , step one is performed once, and then step two is performed once, then both are repeated until policy converges. Then step one is again performed once and so on. (Policy iteration was invented by Howard to optimize Sears catalogue mailing, which he had been optimizing using value iteration.) Instead of repeating step two to convergence, it may be formulated and solved as a set of linear equations. These equations are merely obtained by making in the step two equation. Thus, repeating step two to convergence can be interpreted as solving the linear equations by relaxation. This variant has the advantage that there is a definite stopping condition: when the array does not change in the course of applying step 1 to all states, the algorithm is completed. Policy iteration is usually slower than value iteration for a large number of possible states.

In modified policy iteration (; ), step one is performed once, and then step two is repeated several times. Then step one is again performed once and so on.

In this variant, the steps are preferentially applied to states which are in some way important – whether based on the algorithm (there were large changes in or around those states recently) or based on use (those states are near the starting state, or otherwise of interest to the person or program using the algorithm).

Algorithms for finding optimal policies with time complexity polynomial in the size of the problem representation exist for finite MDPs. Thus, decision problems based on MDPs are in computational complexity class P. 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.

A Markov decision process is a stochastic game with only one player.

The solution above assumes that the state is known when action is to be taken; otherwise cannot be calculated. When this assumption is not true, the problem is called a partially observable Markov decision process or POMDP.