#include <cdynamicprogramming.h>
Inheritance diagram for CValueIteration:
Value Iteration calculates the Value Function of a arbitrary
policy for a given learning problem, it expects a given stochastic
model of the learning problem, so if you need to learn the model as
well, use the prioritized sweeping algorithm. The Value iteration
classes of the toolbox provides both, V-Function learning and
Q-Function learning. Value iteration uses the update rule
V_{k+1}=sum_a pi(s,a)*sum_{s'}P(s'|s,a)*(R(s,a,s')+gamma* V_(s'))
(where pi is a stochastic policy) for value function learning and
Q(s,a)= sum_{s'}P(s'|s,a)*(R(s,a,s')+gamma* V_(s')), where $V_k(s')
= sum_a Q(s',a)*pi(s',a)$ for the Q-Value learning case. If you
repeat that step arbitrary often, the update rule converges to the
value function of the policy. Usually a greedy policy is used for
learning, since you want the optimal value function, but you can
also choose to evaluate the value function of some other, maybe
self-coded policy (as long as it implements the interface
CStochasticPolicy). Dynamic
Programming approaches are usually a safe tool to gather the
optimal value function, but it is also a very CPU-intensive task,
so it is very important which state is updated because in the most
states the update is very small or even zero. So the class
CValueIteration also maintains a priority list of the states,
indicating which state has to be updated first. If a state is
updated according to the given rules, the error of the former value
is calculated and than every state in the backward list of the
updated state from the stochastic model (so every state which leads
to the updated state), gets his priority added by the value error *
prop, where prop is the probability of that (backward) transition.
This concept comes from prioritized sweeping. Due to this concept
the states which are likely to change their Values considerably
gets updated first. The class provides functions for updating the
states in the priority list k times (if the list is empty a random
state is chosen), update the states until the list is empty, or
update a single given state. To give the algorithm a little hint
where to start you can also update all features in the backward
transitions of a specific state. For the priority List the
algorithm uses a sorted feature list.
Creates the Value Iteration algorithm with Q-Function learning
and a greedy policy.
Creates the Value Iteration algorithm with Q-Function learning
and given policy for policy evaluation.
[virtual]
Add all Priorities of the featuers in the feature
list.
Adds the given priority to the given
feature.
Updates all backward states of the given state.
Used to give the algorithm a hint where to start, since due to
the updates, all backward states of the backward states gets added
to the prioritylist (as long as they made a Bellman
error.
updates the frist k states in the priority list
If the list is empty, a random state is
chosen
Updates the states from the priority list until it is
empty.
[protected,
virtual]
returns the priority of a specific Transition given the bellman
error
The standard priority calculation is trans->getProbapility()
* bellE, but this can be changed by possible
subclasses
[protected]
Updates the given feature.
Clears the feature from the prioritylist and then makes either a
Q-Function or a V-Function update. The update process works as
follows:
Updates the first feature from the list.
The actions used by the value iteration.
Temporary state object.
use V or Q Function?
the model
Sorted list of the priorities.
The used Q-Function.
Q-Function for the Action Value calculation when using
V-Learning.
reward function of the learning Problem
The stochastic Policy which is used.
The used V-Function.
V-Function used for the new Value calculation when using
V-Function Learning.