orbital.algorithm.template
Class MarkovDecisionProcess

java.lang.Object
  orbital.algorithm.template.MarkovDecisionProcess

All Implemented Interfaces:

java.io.Serializable, AlgorithmicTemplate

Direct Known Subclasses:

MarkovDecisionProcess.DynamicProgramming

public abstract class MarkovDecisionProcess
extends java.lang.Object
implements AlgorithmicTemplate, java.io.Serializable

Markov decision process (MDP). For closed-loop planning.

Let γ∈[0,1] be a discount factor and π:S→A(s) a policy.

expected cost sum

One evaluation function (or cost function or utility function or value function) f_π corresponding to the policy π is f_π:S→R; f_π(s) = E[∑^∞_t=0 γ^tc(s_t,a_t) | s₀=s,π] i.e. the expected value of the discounted immediate cost sum starting from state s under policy π.

Q-values

The action-value cost of an action a∈A(s) in state s∈S as evaluated by f:S→R is Q_f:S×A(s)→R; Q_f(s,a) = c(s,a) + γ*E[f(s_t+1)|s_t=s,a_t=a]
= c(s,a) + γ*∑_s'∈S P(s'|s,a)*f(s') If f=f_π, Q_fπ(s,a) is the expected cost of performing action a∈A(s) in state s∈S and thereafter following the policy π.

greedy policy

A policy π is greedy with respect to an action-value function Q:S×A(s)→R if ∀s∈S Q(s,π(s)) = min_a∈A(s) Q(s,a) Given an action-value function Q:S×A(s)→R, one greedy policy π_Q with respect to Q is given by π_Q(s) = argmin_a∈A(s) Q(s,a) Similarly, π_f := π_Qf is one greedy policy with respect to an evaluation function f:S→R.

A solution π^* is optimal if it has minimum expected cost (alias maximum expected utility), i.e. f_π^* = f^* ∧ π_f^* = π^*. It is

f^*:S→R is the optimal evaluation function ⇔ f^*(s) = min_a∈A(s) Q_f^*(s,a)

Which is one form of the Bellman optimality equation.

By the way, a minor generalization is sometimes used that would change a policy to be a stochastic function π:S×A→[0,1] specifying the probability π(s,a) with that it chooses the action a∈A(s) in state s∈S. But this does not usually improve the quality of solution policies.

To apply MDP planning, perform something like:

 MarkovDecisionProcess planner = ...;
 // obtain a plan
 Function plan = planner.solve(problem);
 // follow the plan
 for (Object state = initial; !problem.isSolution(state); state = observe()) {
     perform(plan.apply(state));
 }
 

Author:

André Platzer

See Also:

MarkovDecisionProblem, Hector Geffner. Modelling and Problem Solving, "A. Barto, S. Bradtke, and S. Singh. Learning to act using real-time dynamic programming. Artificial Intelligence, 72:81-138, 1995.", Serialized Form

Nested Class Summary

static class

MarkovDecisionProcess.DynamicProgramming Abstract base class for Markov decision processes solved per dynamic programming.

Nested classes/interfaces inherited from interface orbital.algorithm.template.AlgorithmicTemplate

AlgorithmicTemplate.Configuration

Constructor Summary

MarkovDecisionProcess()

Method Summary

protected MarkovDecisionProblem	getProblem() Get the current problem.
protected abstract Function	plan() Run the planning.
java.lang.Object	solve(AlgorithmicProblem p) Solves an MDP problem.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Methods inherited from interface orbital.algorithm.template.AlgorithmicTemplate

complexity, spaceComplexity

Constructor Detail

MarkovDecisionProcess

public MarkovDecisionProcess()

Method Detail

getProblem

protected final MarkovDecisionProblem getProblem()

Get the current problem.

Returns:

the problem specified in the last call to solve.

solve

public java.lang.Object solve(AlgorithmicProblem p)

Solves an MDP problem.

Specified by:

solve in interface AlgorithmicTemplate

Parameters:

p - algorithmic problem hook class which must fit the concrete algorithmic template framework implementation.

Returns:

the solution policy function S→A found, or null if no solution could be found.

See Also:

Function.apply(Object)

plan

protected abstract Function plan()

Run the planning.

Returns:

the solution policy function S→A found, or null if no solution could be found.