mdp.py 56.9 KB
Newer Older
Steven Cordwell's avatar
Steven Cordwell committed
1
# -*- coding: utf-8 -*-
Steven Cordwell's avatar
Steven Cordwell committed
2
"""Markov Decision Process (MDP) Toolbox
3
=====================================
4

Steven Cordwell's avatar
Steven Cordwell committed
5
6
The MDP toolbox provides classes and functions for the resolution of
descrete-time Markov Decision Processes.
Steven Cordwell's avatar
Steven Cordwell committed
7

Steven Cordwell's avatar
Steven Cordwell committed
8
9
10
11
12
Available classes
-----------------
MDP
    Base Markov decision process class
FiniteHorizon
Steven Cordwell's avatar
Steven Cordwell committed
13
    Backwards induction finite horizon MDP
Steven Cordwell's avatar
Steven Cordwell committed
14
15
16
17
18
19
20
21
22
23
24
25
26
27
LP
    Linear programming MDP
PolicyIteration
    Policy iteration MDP
PolicyIterationModified
    Modified policy iteration MDP
QLearning
    Q-learning MDP
RelativeValueIteration
    Relative value iteration MDP
ValueIteration
    Value iteration MDP
ValueIterationGS
    Gauss-Seidel value iteration MDP
Steven Cordwell's avatar
Steven Cordwell committed
28

Steven Cordwell's avatar
Steven Cordwell committed
29
30
31
32
33
34
35
36
37
38
Available functions
-------------------
check
    Check that an MDP is properly defined
checkSquareStochastic
    Check that a matrix is square and stochastic
exampleForest
    A simple forest management example
exampleRand
    A random example
Steven Cordwell's avatar
Steven Cordwell committed
39

Steven Cordwell's avatar
Steven Cordwell committed
40
41
42
43
44
How to use the documentation
----------------------------
Documentation is available both as docstrings provided with the code and
in html or pdf format from 
`The MDP toolbox homepage <http://www.somewhere.com>`_. The docstring
45
examples assume that the `mdp` module has been imported imported like so::
Steven Cordwell's avatar
Steven Cordwell committed
46

47
  >>> import mdptoolbox.mdp as mdp
Steven Cordwell's avatar
Steven Cordwell committed
48
49
50
51
52

Code snippets are indicated by three greater-than signs::

  >>> x = 17
  >>> x = x + 1
53
54
  >>> x
  18
Steven Cordwell's avatar
Steven Cordwell committed
55
56
57
58
59

The documentation can be displayed with
`IPython <http://ipython.scipy.org>`_. For example, to view the docstring of
the ValueIteration class use ``mdp.ValueIteration?<ENTER>``, and to view its
source code use ``mdp.ValueIteration??<ENTER>``.
60

61
62
63
Acknowledgments
---------------
This module is modified from the MDPtoolbox (c) 2009 INRA available at 
Steven Cordwell's avatar
Steven Cordwell committed
64
http://www.inra.fr/mia/T/MDPtoolbox/.
65

Steven Cordwell's avatar
Steven Cordwell committed
66
67
"""

68
69
# Copyright (c) 2011-2013 Steven A. W. Cordwell
# Copyright (c) 2009 INRA
Steven Cordwell's avatar
Steven Cordwell committed
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
# 
# All rights reserved.
# 
# Redistribution and use in source and binary forms, with or without
# modification, are permitted provided that the following conditions are met:
# 
#   * Redistributions of source code must retain the above copyright notice,
#     this list of conditions and the following disclaimer.
#   * Redistributions in binary form must reproduce the above copyright notice,
#     this list of conditions and the following disclaimer in the documentation
#     and/or other materials provided with the distribution.
#   * Neither the name of the <ORGANIZATION> nor the names of its contributors
#     may be used to endorse or promote products derived from this software
#     without specific prior written permission.
# 
# THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
# AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
# IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
# ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
# LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
# CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
# SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
# INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
# CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
# ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
# POSSIBILITY OF SUCH DAMAGE.

Steven Cordwell's avatar
Steven Cordwell committed
97
98
99
from math import ceil, log, sqrt
from time import time

100
101
from numpy import absolute, array, empty, mean, mod, multiply
from numpy import ndarray, ones, zeros
102
from numpy.random import randint, random
Steven Cordwell's avatar
Steven Cordwell committed
103
from scipy.sparse import csr_matrix as sparse
Steven Cordwell's avatar
Steven Cordwell committed
104

105
from utils import check, getSpan
106

Steven Cordwell's avatar
Steven Cordwell committed
107
class MDP(object):
108
    
Steven Cordwell's avatar
Steven Cordwell committed
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
    """A Markov Decision Problem.
    
    Parameters
    ----------
    transitions : array
            transition probability matrices
    reward : array
            reward matrices
    discount : float or None
            discount factor
    epsilon : float or None
            stopping criteria
    max_iter : int or None
            maximum number of iterations
    
    Attributes
    ----------
    P : array
        Transition probability matrices
    R : array
        Reward matrices
    V : list
        Value function
    discount : float
        b
    max_iter : int
        a
    policy : list
        a
    time : float
        a
    verbose : logical
        a
    
    Methods
    -------
    iterate
        To be implemented in child classes, raises exception
    setSilent
        Turn the verbosity off
    setVerbose
        Turn the verbosity on
    
    """
Steven Cordwell's avatar
Steven Cordwell committed
153
    
154
    def __init__(self, transitions, reward, discount, epsilon, max_iter):
155
        # Initialise a MDP based on the input parameters.
156
        
Steven Cordwell's avatar
Steven Cordwell committed
157
158
        # if the discount is None then the algorithm is assumed to not use it
        # in its computations
159
        if type(discount) in (int, float):
Steven Cordwell's avatar
Steven Cordwell committed
160
            if (discount <= 0) or (discount > 1):
161
                raise ValueError("Discount rate must be in ]0; 1]")
Steven Cordwell's avatar
Steven Cordwell committed
162
            else:
Steven Cordwell's avatar
Steven Cordwell committed
163
                if discount == 1:
164
165
166
                    print("PyMDPtoolbox WARNING: check conditions of "
                          "convergence. With no discount, convergence is not "
                          "always assumed.")
Steven Cordwell's avatar
Steven Cordwell committed
167
                self.discount = discount
168
        elif discount is not None:
169
170
            raise ValueError("PyMDPtoolbox: the discount must be a positive "
                             "real number less than or equal to one.")
Steven Cordwell's avatar
Steven Cordwell committed
171
172
        # if the max_iter is None then the algorithm is assumed to not use it
        # in its computations
173
174
        if type(max_iter) in (int, float):
            if max_iter <= 0:
175
176
                raise ValueError("The maximum number of iterations must be "
                                 "greater than 0")
Steven Cordwell's avatar
Steven Cordwell committed
177
178
            else:
                self.max_iter = max_iter
179
        elif max_iter is not None:
180
181
            raise ValueError("PyMDPtoolbox: max_iter must be a positive real "
                             "number greater than zero.")
Steven Cordwell's avatar
Steven Cordwell committed
182
        # check that epsilon is something sane
183
184
        if type(epsilon) in (int, float):
            if epsilon <= 0:
185
186
                raise ValueError("PyMDPtoolbox: epsilon must be greater than "
                                 "0.")
187
        elif epsilon is not None:
188
189
            raise ValueError("PyMDPtoolbox: epsilon must be a positive real "
                             "number greater than zero.")
Steven Cordwell's avatar
Steven Cordwell committed
190
191
192
193
        # we run a check on P and R to make sure they are describing an MDP. If
        # an exception isn't raised then they are assumed to be correct.
        check(transitions, reward)
        # computePR will assign the variables self.S, self.A, self.P and self.R
194
        self._computePR(transitions, reward)
Steven Cordwell's avatar
Steven Cordwell committed
195
196
197
198
        # the verbosity is by default turned off
        self.verbose = False
        # Initially the time taken to perform the computations is set to None
        self.time = None
199
200
        # set the initial iteration count to zero
        self.iter = 0
Steven Cordwell's avatar
Steven Cordwell committed
201
        # V should be stored as a vector ie shape of (S,) or (1, S)
Steven Cordwell's avatar
Steven Cordwell committed
202
        self.V = None
Steven Cordwell's avatar
Steven Cordwell committed
203
        # policy can also be stored as a vector
Steven Cordwell's avatar
Steven Cordwell committed
204
        self.policy = None
Steven Cordwell's avatar
Steven Cordwell committed
205
    
206
207
208
209
210
211
212
213
    def __repr__(self):
        P_repr = "P: \n"
        R_repr = "R: \n"
        for aa in range(self.A):
            P_repr += repr(self.P[aa]) + "\n"
            R_repr += repr(self.R[aa]) + "\n"
        print(P_repr + "\n" + R_repr)
    
214
    def _bellmanOperator(self, V=None):
Steven Cordwell's avatar
Steven Cordwell committed
215
        # Apply the Bellman operator on the value function.
216
        # 
Steven Cordwell's avatar
Steven Cordwell committed
217
        # Updates the value function and the Vprev-improving policy.
218
        # 
Steven Cordwell's avatar
Steven Cordwell committed
219
220
221
222
        # Returns: (policy, value), tuple of new policy and its value
        #
        # If V hasn't been sent into the method, then we assume to be working
        # on the objects V attribute
223
224
        if V is None:
            # this V should be a reference to the data rather than a copy
225
226
            V = self.V
        else:
Steven Cordwell's avatar
Steven Cordwell committed
227
            # make sure the user supplied V is of the right shape
228
            try:
Steven Cordwell's avatar
Steven Cordwell committed
229
                if V.shape not in ((self.S,), (1, self.S)):
230
                    raise ValueError("bellman: V is not the right shape.")
231
232
            except AttributeError:
                raise TypeError("bellman: V must be a numpy array or matrix.")
233
234
235
236
        # Looping through each action the the Q-value matrix is calculated.
        # P and V can be any object that supports indexing, so it is important
        # that you know they define a valid MDP before calling the
        # _bellmanOperator method. Otherwise the results will be meaningless.
Steven Cordwell's avatar
Steven Cordwell committed
237
        Q = empty((self.A, self.S))
Steven Cordwell's avatar
Steven Cordwell committed
238
        for aa in range(self.A):
Steven Cordwell's avatar
Steven Cordwell committed
239
            Q[aa] = self.R[aa] + self.discount * self.P[aa].dot(V)
Steven Cordwell's avatar
Steven Cordwell committed
240
        # Get the policy and value, for now it is being returned but...
241
        # Which way is better?
242
        # 1. Return, (policy, value)
243
        return (Q.argmax(axis=0), Q.max(axis=0))
Steven Cordwell's avatar
Steven Cordwell committed
244
245
        # 2. update self.policy and self.V directly
        # self.V = Q.max(axis=1)
246
        # self.policy = Q.argmax(axis=1)
Steven Cordwell's avatar
Steven Cordwell committed
247
    
248
    def _computePR(self, P, R):
Steven Cordwell's avatar
Steven Cordwell committed
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
        # Compute the reward for the system in one state chosing an action.
        # Arguments
        # ---------
        # Let S = number of states, A = number of actions
        #    P(SxSxA)  = transition matrix 
        #        P could be an array with 3 dimensions or  a cell array (1xA), 
        #        each cell containing a matrix (SxS) possibly sparse
        #    R(SxSxA) or (SxA) = reward matrix
        #        R could be an array with 3 dimensions (SxSxA) or  a cell array 
        #        (1xA), each cell containing a sparse matrix (SxS) or a 2D 
        #        array(SxA) possibly sparse  
        # Evaluation
        # ----------
        #    PR(SxA)   = reward matrix
        #
264
        # We assume that P and R define a MDP i,e. assumption is that
Steven Cordwell's avatar
Steven Cordwell committed
265
        # check(P, R) has already been run and doesn't fail.
266
        #
267
268
        # Set self.P as a tuple of length A, with each element storing an S×S
        # matrix.
Steven Cordwell's avatar
Steven Cordwell committed
269
        self.A = len(P)
270
271
272
        try:
            if P.ndim == 3:
                self.S = P.shape[1]
Steven Cordwell's avatar
Steven Cordwell committed
273
274
            else:
               self.S = P[0].shape[0]
275
        except AttributeError:
Steven Cordwell's avatar
Steven Cordwell committed
276
            self.S = P[0].shape[0]
277
278
279
280
281
        except:
            raise
        # convert Ps to matrices
        self.P = []
        for aa in xrange(self.A):
282
            self.P.append(P[aa])
283
        self.P = tuple(self.P)
Steven Cordwell's avatar
Steven Cordwell committed
284
285
        # Set self.R as a tuple of length A, with each element storing an 1×S
        # vector.
286
        try:
287
            if R.ndim == 2:
288
289
                self.R = []
                for aa in xrange(self.A):
Steven Cordwell's avatar
Steven Cordwell committed
290
                    self.R.append(array(R[:, aa]).reshape(self.S))
Steven Cordwell's avatar
Steven Cordwell committed
291
            else:
292
293
294
295
                raise AttributeError
        except AttributeError:
            self.R = []
            for aa in xrange(self.A):
Steven Cordwell's avatar
Steven Cordwell committed
296
297
298
299
300
301
                try:
                    self.R.append(P[aa].multiply(R[aa]).sum(1).reshape(self.S))
                except AttributeError:
                    self.R.append(multiply(P[aa],R[aa]).sum(1).reshape(self.S))
                except:
                    raise
302
303
304
        except:
            raise
        self.R = tuple(self.R)
305
    
306
    def _iterate(self):
Steven Cordwell's avatar
Steven Cordwell committed
307
        # Raise error because child classes should implement this function.
308
        raise NotImplementedError("You should create an _iterate() method.")
Steven Cordwell's avatar
Steven Cordwell committed
309
    
Steven Cordwell's avatar
Steven Cordwell committed
310
    def setSilent(self):
311
        """Set the MDP algorithm to silent mode."""
Steven Cordwell's avatar
Steven Cordwell committed
312
313
314
        self.verbose = False
    
    def setVerbose(self):
315
        """Set the MDP algorithm to verbose mode."""
Steven Cordwell's avatar
Steven Cordwell committed
316
        self.verbose = True
Steven Cordwell's avatar
Steven Cordwell committed
317
318

class FiniteHorizon(MDP):
319
    
Steven Cordwell's avatar
Steven Cordwell committed
320
    """A MDP solved using the finite-horizon backwards induction algorithm.
Steven Cordwell's avatar
Steven Cordwell committed
321
322
    
    Let S = number of states, A = number of actions
Steven Cordwell's avatar
Steven Cordwell committed
323
324
325
    
    Parameters
    ----------
Steven Cordwell's avatar
Steven Cordwell committed
326
    P(SxSxA) = transition matrix 
327
328
             P could be an array with 3 dimensions ora cell array (1xA),
             each cell containing a matrix (SxS) possibly sparse
Steven Cordwell's avatar
Steven Cordwell committed
329
330
331
332
333
334
335
    R(SxSxA) or (SxA) = reward matrix
             R could be an array with 3 dimensions (SxSxA) or 
             a cell array (1xA), each cell containing a sparse matrix (SxS) or
             a 2D array(SxA) possibly sparse  
    discount = discount factor, in ]0, 1]
    N        = number of periods, upper than 0
    h(S)     = terminal reward, optional (default [0; 0; ... 0] )
Steven Cordwell's avatar
Steven Cordwell committed
336
337
    
    Attributes
Steven Cordwell's avatar
Steven Cordwell committed
338
    ----------
Steven Cordwell's avatar
Steven Cordwell committed
339
340
341
    
    Methods
    -------
Steven Cordwell's avatar
Steven Cordwell committed
342
343
344
345
346
347
348
349
350
351
352
353
354
    V(S,N+1)     = optimal value function
                 V(:,n) = optimal value function at stage n
                        with stage in 1, ..., N
                        V(:,N+1) = value function for terminal stage 
    policy(S,N)  = optimal policy
                 policy(:,n) = optimal policy at stage n
                        with stage in 1, ...,N
                        policy(:,N) = policy for stage N
    cpu_time = used CPU time
  
    Notes
    -----
    In verbose mode, displays the current stage and policy transpose.
355
    
Steven Cordwell's avatar
Steven Cordwell committed
356
357
    Examples
    --------
358
359
360
    >>> import mdptoolbox, mdptoolbox.example
    >>> P, R = mdptoolbox.example.forest()
    >>> fh = mdptoolbox.mdp.FiniteHorizon(P, R, 0.9, 3)
Steven Cordwell's avatar
Steven Cordwell committed
361
362
363
364
365
366
367
368
    >>> fh.V
    array([[ 2.6973,  0.81  ,  0.    ,  0.    ],
           [ 5.9373,  3.24  ,  1.    ,  0.    ],
           [ 9.9373,  7.24  ,  4.    ,  0.    ]])
    >>> fh.policy
    array([[0, 0, 0],
           [0, 0, 1],
           [0, 0, 0]])
369
    
Steven Cordwell's avatar
Steven Cordwell committed
370
    """
Steven Cordwell's avatar
Steven Cordwell committed
371

Steven Cordwell's avatar
Steven Cordwell committed
372
    def __init__(self, transitions, reward, discount, N, h=None):
373
        # Initialise a finite horizon MDP.
Steven Cordwell's avatar
Steven Cordwell committed
374
        if N < 1:
Steven Cordwell's avatar
Steven Cordwell committed
375
            raise ValueError('PyMDPtoolbox: N must be greater than 0')
Steven Cordwell's avatar
Steven Cordwell committed
376
        else:
Steven Cordwell's avatar
Steven Cordwell committed
377
            self.N = N
Steven Cordwell's avatar
Steven Cordwell committed
378
        # Initialise the base class
379
        MDP.__init__(self, transitions, reward, discount, None, None)
Steven Cordwell's avatar
Steven Cordwell committed
380
381
        # remove the iteration counter, it is not meaningful for backwards
        # induction
382
        del self.iter
Steven Cordwell's avatar
Steven Cordwell committed
383
        # There are value vectors for each time step up to the horizon
384
        self.V = zeros((self.S, N + 1))
Steven Cordwell's avatar
Steven Cordwell committed
385
386
387
388
389
        # There are policy vectors for each time step before the horizon, when
        # we reach the horizon we don't need to make decisions anymore.
        self.policy = empty((self.S, N), dtype=int)
        # Set the reward for the final transition to h, if specified.
        if h is not None:
390
            self.V[:, N] = h
391
392
393
394
        # Call the iteration method
        self._iterate()
        
    def _iterate(self):
Steven Cordwell's avatar
Steven Cordwell committed
395
        # Run the finite horizon algorithm.
Steven Cordwell's avatar
Steven Cordwell committed
396
        self.time = time()
Steven Cordwell's avatar
Steven Cordwell committed
397
        # loop through each time period
398
        for n in range(self.N):
Steven Cordwell's avatar
Steven Cordwell committed
399
400
401
            W, X = self._bellmanOperator(self.V[:, self.N - n])
            self.V[:, self.N - n - 1] = X
            self.policy[:, self.N - n - 1] = W
Steven Cordwell's avatar
Steven Cordwell committed
402
            if self.verbose:
403
404
                print("stage: %s ... policy transpose : %s") % (
                    self.N - n, self.policy[:, self.N - n -1].tolist())
Steven Cordwell's avatar
Steven Cordwell committed
405
        # update time spent running
Steven Cordwell's avatar
Steven Cordwell committed
406
        self.time = time() - self.time
Steven Cordwell's avatar
Steven Cordwell committed
407
408
409
410
411
412
413
414
415
416
        # After this we could create a tuple of tuples for the values and 
        # policies.
        #V = []
        #p = []
        #for n in xrange(self.N):
        #    V.append()
        #    p.append()
        #V.append()
        #self.V = tuple(V)
        #self.policy = tuple(p)
Steven Cordwell's avatar
Steven Cordwell committed
417
418

class LP(MDP):
419
    
420
    """A discounted MDP soloved using linear programming.
Steven Cordwell's avatar
Steven Cordwell committed
421
422
423
424
425

    Arguments
    ---------
    Let S = number of states, A = number of actions
    P(SxSxA) = transition matrix 
426
427
             P could be an array with 3 dimensions or a cell array (1xA),
             each cell containing a matrix (SxS) possibly sparse
Steven Cordwell's avatar
Steven Cordwell committed
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
    R(SxSxA) or (SxA) = reward matrix
             R could be an array with 3 dimensions (SxSxA) or 
             a cell array (1xA), each cell containing a sparse matrix (SxS) or
             a 2D array(SxA) possibly sparse  
    discount = discount rate, in ]0; 1[
    h(S)     = terminal reward, optional (default [0; 0; ... 0] )
    
    Evaluation
    ----------
    V(S)   = optimal values
    policy(S) = optimal policy
    cpu_time = used CPU time
    
    Notes    
    -----
    In verbose mode, displays the current stage and policy transpose.
    
    Examples
    --------
447
448
449
    >>> import mdptoolbox, mdptoolbox.example
    >>> P, R = mdptoolbox.example.forest()
    >>> lp = mdptoolbox.mdp.LP(P, R, 0.9)
450
    
Steven Cordwell's avatar
Steven Cordwell committed
451
    """
Steven Cordwell's avatar
Steven Cordwell committed
452

Steven Cordwell's avatar
Steven Cordwell committed
453
    def __init__(self, transitions, reward, discount):
454
        # Initialise a linear programming MDP.
Steven Cordwell's avatar
Steven Cordwell committed
455
        # import some functions from cvxopt and set them as object methods
Steven Cordwell's avatar
Steven Cordwell committed
456
457
        try:
            from cvxopt import matrix, solvers
458
459
            self._linprog = solvers.lp
            self._cvxmat = matrix
Steven Cordwell's avatar
Steven Cordwell committed
460
        except ImportError:
461
462
            raise ImportError("The python module cvxopt is required to use "
                              "linear programming functionality.")
Steven Cordwell's avatar
Steven Cordwell committed
463
464
        # we also need diagonal matrices, and using a sparse one may be more
        # memory efficient
Steven Cordwell's avatar
Steven Cordwell committed
465
        from scipy.sparse import eye as speye
466
        self._speye = speye
Steven Cordwell's avatar
Steven Cordwell committed
467
        # initialise the MDP. epsilon and max_iter are not needed
468
        MDP.__init__(self, transitions, reward, discount, None, None)
Steven Cordwell's avatar
Steven Cordwell committed
469
        # Set the cvxopt solver to be quiet by default, but ...
470
        # this doesn't do what I want it to do c.f. issue #3
471
472
        if not self.verbose:
            solvers.options['show_progress'] = False
473
474
        # Call the iteration method
        self._iterate()
475
    
476
    def _iterate(self):
Steven Cordwell's avatar
Steven Cordwell committed
477
        #Run the linear programming algorithm.
478
        self.time = time()
Steven Cordwell's avatar
Steven Cordwell committed
479
        # The objective is to resolve : min V / V >= PR + discount*P*V
480
481
        # The function linprog of the optimisation Toolbox of Mathworks
        # resolves :
Steven Cordwell's avatar
Steven Cordwell committed
482
        # min f'* x / M * x <= b
483
484
485
486
        # So the objective could be expressed as :
        # min V / (discount*P-I) * V <= - PR
        # To avoid loop on states, the matrix M is structured following actions
        # M(A*S,S)
487
488
489
        f = self._cvxmat(ones((self.S, 1)))
        h = self._cvxmat(self.R.reshape(self.S * self.A, 1, order="F"), tc='d')
        M = zeros((self.A * self.S, self.S))
Steven Cordwell's avatar
Steven Cordwell committed
490
491
        for aa in range(self.A):
            pos = (aa + 1) * self.S
492
493
494
            M[(pos - self.S):pos, :] = (
                self.discount * self.P[aa] - self._speye(self.S, self.S))
        M = self._cvxmat(M)
495
496
497
        # Using the glpk option will make this behave more like Octave
        # (Octave uses glpk) and perhaps Matlab. If solver=None (ie using the 
        # default cvxopt solver) then V agrees with the Octave equivalent
Steven Cordwell's avatar
Steven Cordwell committed
498
        # only to 10e-8 places. This assumes glpk is installed of course.
Steven Cordwell's avatar
Steven Cordwell committed
499
        self.V = array(self._linprog(f, M, -h, solver='glpk')['x'])
Steven Cordwell's avatar
Steven Cordwell committed
500
        # apply the Bellman operator
501
        self.policy, self.V =  self._bellmanOperator()
Steven Cordwell's avatar
Steven Cordwell committed
502
        # update the time spent solving
Steven Cordwell's avatar
Steven Cordwell committed
503
        self.time = time() - self.time
504
        # store value and policy as tuples
505
506
        self.V = tuple(self.V.tolist())
        self.policy = tuple(self.policy.tolist())
Steven Cordwell's avatar
Steven Cordwell committed
507
508

class PolicyIteration(MDP):
509
    
510
    """A discounted MDP solved using the policy iteration algorithm.
Steven Cordwell's avatar
Steven Cordwell committed
511
    
Steven Cordwell's avatar
Steven Cordwell committed
512
513
514
515
    Arguments
    ---------
    Let S = number of states, A = number of actions
    P(SxSxA) = transition matrix 
516
517
             P could be an array with 3 dimensions or a cell array (1xA),
             each cell containing a matrix (SxS) possibly sparse
Steven Cordwell's avatar
Steven Cordwell committed
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
    R(SxSxA) or (SxA) = reward matrix
             R could be an array with 3 dimensions (SxSxA) or 
             a cell array (1xA), each cell containing a sparse matrix (SxS) or
             a 2D array(SxA) possibly sparse  
    discount = discount rate, in ]0, 1[
    policy0(S) = starting policy, optional 
    max_iter = maximum number of iteration to be done, upper than 0, 
             optional (default 1000)
    eval_type = type of function used to evaluate policy: 
             0 for mdp_eval_policy_matrix, else mdp_eval_policy_iterative
             optional (default 0)
             
    Evaluation
    ----------
    V(S)   = value function 
    policy(S) = optimal policy
    iter     = number of done iterations
    cpu_time = used CPU time
    
    Notes
    -----
    In verbose mode, at each iteration, displays the number 
    of differents actions between policy n-1 and n
    
Steven Cordwell's avatar
Steven Cordwell committed
542
543
    Examples
    --------
544
545
546
    >>> import mdptoolbox, mdptoolbox.example
    >>> P, R = mdptoolbox.example.rand()
    >>> pi = mdptoolbox.mdp.PolicyIteration(P, R, 0.9)
547
    
548
549
    >>> P, R = mdptoolbox.example.forest()
    >>> pi = mdptoolbox.mdp.PolicyIteration(P, R, 0.9)
Steven Cordwell's avatar
Steven Cordwell committed
550
    >>> pi.V
551
    (26.244000000000018, 29.48400000000002, 33.484000000000016)
Steven Cordwell's avatar
Steven Cordwell committed
552
    >>> pi.policy
553
    (0, 0, 0)
Steven Cordwell's avatar
Steven Cordwell committed
554
    """
Steven Cordwell's avatar
Steven Cordwell committed
555
    
556
557
    def __init__(self, transitions, reward, discount, policy0=None,
                 max_iter=1000, eval_type=0):
Steven Cordwell's avatar
Steven Cordwell committed
558
559
560
        # Initialise a policy iteration MDP.
        #
        # Set up the MDP, but don't need to worry about epsilon values
561
        MDP.__init__(self, transitions, reward, discount, None, max_iter)
Steven Cordwell's avatar
Steven Cordwell committed
562
        # Check if the user has supplied an initial policy. If not make one.
Steven Cordwell's avatar
Steven Cordwell committed
563
        if policy0 == None:
Steven Cordwell's avatar
Steven Cordwell committed
564
            # Initialise the policy to the one which maximises the expected
Steven Cordwell's avatar
Steven Cordwell committed
565
            # immediate reward
Steven Cordwell's avatar
Steven Cordwell committed
566
567
            null = zeros(self.S)
            self.policy, null = self._bellmanOperator(null)
568
            del null
Steven Cordwell's avatar
Steven Cordwell committed
569
        else:
Steven Cordwell's avatar
Steven Cordwell committed
570
571
            # Use the policy that the user supplied
            # Make sure it is a numpy array
Steven Cordwell's avatar
Steven Cordwell committed
572
            policy0 = array(policy0)
Steven Cordwell's avatar
Steven Cordwell committed
573
            # Make sure the policy is the right size and shape
Steven Cordwell's avatar
Steven Cordwell committed
574
            if not policy0.shape in ((self.S, ), (self.S, 1), (1, self.S)):
575
576
                raise ValueError("PyMDPtolbox: policy0 must a vector with "
                                 "length S.")
Steven Cordwell's avatar
Steven Cordwell committed
577
            # reshape the policy to be a vector
Steven Cordwell's avatar
Steven Cordwell committed
578
            policy0 = policy0.reshape(self.S)
Steven Cordwell's avatar
Steven Cordwell committed
579
            # The policy can only contain integers between 1 and S
580
581
582
583
            if (mod(policy0, 1).any() or (policy0 < 0).any() or
                    (policy0 >= self.S).any()):
                raise ValueError("PyMDPtoolbox: policy0 must be a vector of "
                                 "integers between 1 and S.")
Steven Cordwell's avatar
Steven Cordwell committed
584
585
            else:
                self.policy = policy0
Steven Cordwell's avatar
Steven Cordwell committed
586
        # set the initial values to zero
Steven Cordwell's avatar
Steven Cordwell committed
587
        self.V = zeros(self.S)
Steven Cordwell's avatar
Steven Cordwell committed
588
        # Do some setup depending on the evaluation type
Steven Cordwell's avatar
Steven Cordwell committed
589
        if eval_type in (0, "matrix"):
590
            from numpy.linalg import solve
591
            from scipy.sparse import eye
592
593
            self._speye = eye
            self._lin_eq = solve
Steven Cordwell's avatar
Steven Cordwell committed
594
595
596
597
            self.eval_type = "matrix"
        elif eval_type in (1, "iterative"):
            self.eval_type = "iterative"
        else:
598
599
600
601
            raise ValueError("PyMDPtoolbox: eval_type should be 0 for matrix "
                             "evaluation or 1 for iterative evaluation. "
                             "The strings 'matrix' and 'iterative' can also "
                             "be used.")
602
603
        # Call the iteration method
        self._iterate()
Steven Cordwell's avatar
Steven Cordwell committed
604
    
605
    def _computePpolicyPRpolicy(self):
Steven Cordwell's avatar
Steven Cordwell committed
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
        # Compute the transition matrix and the reward matrix for a policy.
        #
        # Arguments
        # ---------
        # Let S = number of states, A = number of actions
        # P(SxSxA)  = transition matrix 
        #     P could be an array with 3 dimensions or a cell array (1xA),
        #     each cell containing a matrix (SxS) possibly sparse
        # R(SxSxA) or (SxA) = reward matrix
        #     R could be an array with 3 dimensions (SxSxA) or 
        #     a cell array (1xA), each cell containing a sparse matrix (SxS) or
        #     a 2D array(SxA) possibly sparse  
        # policy(S) = a policy
        #
        # Evaluation
        # ----------
        # Ppolicy(SxS)  = transition matrix for policy
        # PRpolicy(S)   = reward matrix for policy
        #
Steven Cordwell's avatar
Steven Cordwell committed
625
626
        Ppolicy = empty((self.S, self.S))
        Rpolicy = zeros(self.S)
Steven Cordwell's avatar
Steven Cordwell committed
627
        for aa in range(self.A): # avoid looping over S
Steven Cordwell's avatar
Steven Cordwell committed
628
629
            # the rows that use action a.
            ind = (self.policy == aa).nonzero()[0]
630
631
            # if no rows use action a, then no need to assign this
            if ind.size > 0:
Steven Cordwell's avatar
Steven Cordwell committed
632
                Ppolicy[ind, :] = self.P[aa][ind, :]
633
                #PR = self._computePR() # an apparently uneeded line, and
Steven Cordwell's avatar
Steven Cordwell committed
634
635
                # perhaps harmful in this implementation c.f.
                # mdp_computePpolicyPRpolicy.m
636
                Rpolicy[ind] = self.R[aa][ind]
Steven Cordwell's avatar
Steven Cordwell committed
637
638
639
640
641
642
643
644
645
646
        # self.R cannot be sparse with the code in its current condition, but
        # it should be possible in the future. Also, if R is so big that its
        # a good idea to use a sparse matrix for it, then converting PRpolicy
        # from a dense to sparse matrix doesn't seem very memory efficient
        if type(self.R) is sparse:
            Rpolicy = sparse(Rpolicy)
        #self.Ppolicy = Ppolicy
        #self.Rpolicy = Rpolicy
        return (Ppolicy, Rpolicy)
    
647
    def _evalPolicyIterative(self, V0=0, epsilon=0.0001, max_iter=10000):
Steven Cordwell's avatar
Steven Cordwell committed
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
        # Evaluate a policy using iteration.
        #
        # Arguments
        # ---------
        # Let S = number of states, A = number of actions
        # P(SxSxA)  = transition matrix 
        #    P could be an array with 3 dimensions or 
        #    a cell array (1xS), each cell containing a matrix possibly sparse
        # R(SxSxA) or (SxA) = reward matrix
        #    R could be an array with 3 dimensions (SxSxA) or 
        #    a cell array (1xA), each cell containing a sparse matrix (SxS) or
        #    a 2D array(SxA) possibly sparse  
        # discount  = discount rate in ]0; 1[
        # policy(S) = a policy
        # V0(S)     = starting value function, optional (default : zeros(S,1))
        # epsilon   = epsilon-optimal policy search, upper than 0,
        #    optional (default : 0.0001)
        # max_iter  = maximum number of iteration to be done, upper than 0, 
        #    optional (default : 10000)
        #    
        # Evaluation
        # ----------
        # Vpolicy(S) = value function, associated to a specific policy
        #
        # Notes
        # -----
        # In verbose mode, at each iteration, displays the condition which
        # stopped iterations: epsilon-optimum value function found or maximum
        # number of iterations reached.
        #
678
        if (type(V0) in (int, float)) and (V0 == 0):
Steven Cordwell's avatar
Steven Cordwell committed
679
            policy_V = zeros(self.S)
Steven Cordwell's avatar
Steven Cordwell committed
680
        else:
Steven Cordwell's avatar
Steven Cordwell committed
681
            if (type(V0) in (ndarray)) and (V0.shape == (self.S, 1)):
682
683
                policy_V = V0
            else:
684
685
686
                raise ValueError("PyMDPtoolbox: V0 vector/array type not "
                                 "supported. Use ndarray of matrix column "
                                 "vector length S.")
Steven Cordwell's avatar
Steven Cordwell committed
687
        
688
        policy_P, policy_R = self._computePpolicyPRpolicy()
Steven Cordwell's avatar
Steven Cordwell committed
689
690
691
        
        if self.verbose:
            print('  Iteration    V_variation')
692
        
Steven Cordwell's avatar
Steven Cordwell committed
693
694
695
        itr = 0
        done = False
        while not done:
696
            itr += 1
697
698
            
            Vprev = policy_V
699
            policy_V = policy_R + self.discount * policy_P.dot(Vprev)
700
701
            
            variation = absolute(policy_V - Vprev).max()
Steven Cordwell's avatar
Steven Cordwell committed
702
703
            if self.verbose:
                print('      %s         %s') % (itr, variation)
704
705
706
            
            # ensure |Vn - Vpolicy| < epsilon
            if variation < ((1 - self.discount) / self.discount) * epsilon:
Steven Cordwell's avatar
Steven Cordwell committed
707
708
                done = True
                if self.verbose:
709
710
                    print("PyMDPtoolbox: iterations stopped, epsilon-optimal "
                          "value function.")
Steven Cordwell's avatar
Steven Cordwell committed
711
712
713
            elif itr == max_iter:
                done = True
                if self.verbose:
714
715
                    print("PyMDPtoolbox: iterations stopped by maximum number "
                          "of iteration condition.")
Steven Cordwell's avatar
Steven Cordwell committed
716
        
Steven Cordwell's avatar
Steven Cordwell committed
717
        self.V = policy_V
718
    
719
    def _evalPolicyMatrix(self):
Steven Cordwell's avatar
Steven Cordwell committed
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
        # Evaluate the value function of the policy using linear equations.
        #
        # Arguments 
        # ---------
        # Let S = number of states, A = number of actions
        # P(SxSxA) = transition matrix 
        #      P could be an array with 3 dimensions or a cell array (1xA),
        #      each cell containing a matrix (SxS) possibly sparse
        # R(SxSxA) or (SxA) = reward matrix
        #      R could be an array with 3 dimensions (SxSxA) or 
        #      a cell array (1xA), each cell containing a sparse matrix (SxS) or
        #      a 2D array(SxA) possibly sparse  
        # discount = discount rate in ]0; 1[
        # policy(S) = a policy
        #
        # Evaluation
        # ----------
        # Vpolicy(S) = value function of the policy
        #
739
        Ppolicy, Rpolicy = self._computePpolicyPRpolicy()
Steven Cordwell's avatar
Steven Cordwell committed
740
        # V = PR + gPV  => (I-gP)V = PR  => V = inv(I-gP)* PR
741
742
        self.V = self._lin_eq(
            (self._speye(self.S, self.S) - self.discount * Ppolicy), Rpolicy)
Steven Cordwell's avatar
Steven Cordwell committed
743
    
744
    def _iterate(self):
Steven Cordwell's avatar
Steven Cordwell committed
745
746
        # Run the policy iteration algorithm.
        # If verbose the print a header
747
748
        if self.verbose:
            print('  Iteration  Number_of_different_actions')
Steven Cordwell's avatar
Steven Cordwell committed
749
        # Set up the while stopping condition and the current time
Steven Cordwell's avatar
Steven Cordwell committed
750
        done = False
751
        self.time = time()
Steven Cordwell's avatar
Steven Cordwell committed
752
        # loop until a stopping condition is reached
Steven Cordwell's avatar
Steven Cordwell committed
753
        while not done:
754
            self.iter += 1
755
            # these _evalPolicy* functions will update the classes value
Steven Cordwell's avatar
Steven Cordwell committed
756
            # attribute
Steven Cordwell's avatar
Steven Cordwell committed
757
            if self.eval_type == "matrix":
758
                self._evalPolicyMatrix()
Steven Cordwell's avatar
Steven Cordwell committed
759
            elif self.eval_type == "iterative":
760
                self._evalPolicyIterative()
Steven Cordwell's avatar
Steven Cordwell committed
761
762
            # This should update the classes policy attribute but leave the
            # value alone
763
            policy_next, null = self._bellmanOperator()
764
            del null
Steven Cordwell's avatar
Steven Cordwell committed
765
766
            # calculate in how many places does the old policy disagree with
            # the new policy
767
            n_different = (policy_next != self.policy).sum()
Steven Cordwell's avatar
Steven Cordwell committed
768
            # if verbose then continue printing a table
769
            if self.verbose:
770
771
                print('       %s                 %s') % (self.iter,
                                                         n_different)
Steven Cordwell's avatar
Steven Cordwell committed
772
773
            # Once the policy is unchanging of the maximum number of 
            # of iterations has been reached then stop
774
            if n_different == 0:
Steven Cordwell's avatar
Steven Cordwell committed
775
                done = True
776
                if self.verbose:
777
778
                    print("PyMDPtoolbox: iterations stopped, unchanging "
                          "policy found.")
779
780
781
            elif (self.iter == self.max_iter):
                done = True 
                if self.verbose:
782
783
                    print("PyMDPtoolbox: iterations stopped by maximum number "
                          "of iteration condition.")
784
785
            else:
                self.policy = policy_next
Steven Cordwell's avatar
Steven Cordwell committed
786
        # update the time to return th computation time
787
        self.time = time() - self.time
Steven Cordwell's avatar
Steven Cordwell committed
788
        # store value and policy as tuples
789
790
        self.V = tuple(self.V.tolist())
        self.policy = tuple(self.policy.tolist())
Steven Cordwell's avatar
Steven Cordwell committed
791

792
class PolicyIterationModified(PolicyIteration):
793
    
794
    """A discounted MDP  solved using a modifified policy iteration algorithm.
Steven Cordwell's avatar
Steven Cordwell committed
795
796
797
798
799
    
    Arguments
    ---------
    Let S = number of states, A = number of actions
    P(SxSxA) = transition matrix 
800
801
             P could be an array with 3 dimensions or a cell array (1xA),
             each cell containing a matrix (SxS) possibly sparse
Steven Cordwell's avatar
Steven Cordwell committed
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
    R(SxSxA) or (SxA) = reward matrix
             R could be an array with 3 dimensions (SxSxA) or 
             a cell array (1xA), each cell containing a sparse matrix (SxS) or
             a 2D array(SxA) possibly sparse  
    discount = discount rate, in ]0, 1[
    policy0(S) = starting policy, optional 
    max_iter = maximum number of iteration to be done, upper than 0, 
             optional (default 1000)
    eval_type = type of function used to evaluate policy: 
             0 for mdp_eval_policy_matrix, else mdp_eval_policy_iterative
             optional (default 0)
    
    Data Attributes
    ---------------
    V(S)   = value function 
    policy(S) = optimal policy
    iter     = number of done iterations
    cpu_time = used CPU time
    
    Notes
    -----
    In verbose mode, at each iteration, displays the number 
    of differents actions between policy n-1 and n
    
    Examples
    --------
828
829
830
831
832
833
834
    >>> import mdptoolbox, mdptoolbox.example
    >>> P, R = mdptoolbox.example.forest()
    >>> pim = mdptoolbox.mdp.PolicyIterationModified(P, R, 0.9)
    >>> pim.policy
    FIXME
    >>> pim.V
    FIXME
835
    
Steven Cordwell's avatar
Steven Cordwell committed
836
    """
837
    
838
839
    def __init__(self, transitions, reward, discount, epsilon=0.01,
                 max_iter=10):
840
        # Initialise a (modified) policy iteration MDP.
Steven Cordwell's avatar
Steven Cordwell committed
841
        
842
843
844
        # Maybe its better not to subclass from PolicyIteration, because the
        # initialisation of the two are quite different. eg there is policy0
        # being calculated here which doesn't need to be. The only thing that
845
        # is needed from the PolicyIteration class is the _evalPolicyIterative
846
        # function. Perhaps there is a better way to do it?
847
848
        PolicyIteration.__init__(self, transitions, reward, discount, None,
                                 max_iter, 1)
849
        
850
851
852
853
        # PolicyIteration doesn't pass epsilon to MDP.__init__() so we will
        # check it here
        if type(epsilon) in (int, float):
            if epsilon <= 0:
854
855
                raise ValueError("PyMDPtoolbox: epsilon must be greater than "
                                 "0.")
856
        else:
857
858
            raise ValueError("PyMDPtoolbox: epsilon must be a positive real "
                             "number greater than zero.")
859
        
860
861
        # computation of threshold of variation for V for an epsilon-optimal
        # policy
862
863
864
865
866
        if self.discount != 1:
            self.thresh = epsilon * (1 - self.discount) / self.discount
        else:
            self.thresh = epsilon
        
867
868
        self.epsilon = epsilon
        
869
        if discount == 1:
Steven Cordwell's avatar
Steven Cordwell committed
870
            self.V = zeros((self.S, 1))
871
872
        else:
            # min(min()) is not right
873
            self.V = 1 / (1 - discount) * self.R.min() * ones((self.S, 1))
874
875
876
        
        # Call the iteration method
        self._iterate()
Steven Cordwell's avatar
Steven Cordwell committed
877
    
878
    def _iterate(self):
879
        # Run the modified policy iteration algorithm.
880
881
882
883
        
        if self.verbose:
            print('  Iteration  V_variation')
        
Steven Cordwell's avatar
Steven Cordwell committed
884
        self.time = time()
Steven Cordwell's avatar
Steven Cordwell committed
885
        
886
887
        done = False
        while not done:
888
            self.iter += 1
889
            
890
            self.policy, Vnext = self._bellmanOperator()
891
            #[Ppolicy, PRpolicy] = mdp_computePpolicyPRpolicy(P, PR, policy);
892
            
893
            variation = getSpan(Vnext - self.V)
894
895
896
            if self.verbose:
                print("      %s         %s" % (self.iter, variation))
            
Steven Cordwell's avatar
Steven Cordwell committed
897
            self.V = Vnext
Steven Cordwell's avatar
Steven Cordwell committed
898
            if variation < self.thresh:
899
900
901
902
                done = True
            else:
                is_verbose = False
                if self.verbose:
903
                    self.setSilent()
904
905
                    is_verbose = True
                
906
                self._evalPolicyIterative(self.V, self.epsilon, self.max_iter)
907
908
                
                if is_verbose:
909
                    self.setVerbose()
910
        
911
        self.time = time() - self.time
912
913
        
        # store value and policy as tuples
914
915
        self.V = tuple(self.V.tolist())
        self.policy = tuple(self.policy.tolist())
Steven Cordwell's avatar
Steven Cordwell committed
916
917

class QLearning(MDP):
918
    
919
    """A discounted MDP solved using the Q learning algorithm.
Steven Cordwell's avatar
Steven Cordwell committed
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
    
    Let S = number of states, A = number of actions
    
    Parameters
    ----------
    P : transition matrix (SxSxA)
        P could be an array with 3 dimensions or a cell array (1xA), each
        cell containing a sparse matrix (SxS)
    R : reward matrix(SxSxA) or (SxA)
        R could be an array with 3 dimensions (SxSxA) or a cell array
        (1xA), each cell containing a sparse matrix (SxS) or a 2D
        array(SxA) possibly sparse
    discount : discount rate
        in ]0; 1[    
    n_iter : number of iterations to execute (optional).
935
936
        Default value = 10000; it is an integer greater than the default
        value.
Steven Cordwell's avatar
Steven Cordwell committed
937
938
939
940
941
    
    Results
    -------
    Q : learned Q matrix (SxA) 
    
Steven Cordwell's avatar
Steven Cordwell committed
942
    V : learned value function (S).
Steven Cordwell's avatar
Steven Cordwell committed
943
944
945
946
947
948
949
    
    policy : learned optimal policy (S).
    
    mean_discrepancy : vector of V discrepancy mean over 100 iterations
        Then the length of this vector for the default value of N is 100 
        (N/100).

950
    Examples
Steven Cordwell's avatar
Steven Cordwell committed
951
    ---------
952
953
954
    >>> # These examples are reproducible only if random seed is set to 0 in
    >>> # both the random and numpy.random modules.
    >>> import numpy as np
955
    >>> import mdptoolbox, mdptoolbox.example
956
    >>> np.random.seed(0)
957
958
    >>> P, R = mdptoolbox.example.forest()
    >>> ql = mdptoolbox.mdp.QLearning(P, R, 0.96)
Steven Cordwell's avatar
Steven Cordwell committed
959
    >>> ql.Q
960
961
962
    array([[ 68.38037354,  43.24888454],
           [ 72.37777922,  42.75549145],
           [ 77.02892702,  64.68712932]])
Steven Cordwell's avatar
Steven Cordwell committed
963
    >>> ql.V
964
    (68.38037354422798, 72.37777921607258, 77.02892701616531)
Steven Cordwell's avatar
Steven Cordwell committed
965
    >>> ql.policy
966
    (0, 0, 0)
Steven Cordwell's avatar
Steven Cordwell committed
967
    
968
    >>> import mdptoolbox
Steven Cordwell's avatar
Steven Cordwell committed
969
970
971
    >>> import numpy as np
    >>> P = np.array([[[0.5, 0.5],[0.8, 0.2]],[[0, 1],[0.1, 0.9]]])
    >>> R = np.array([[5, 10], [-1, 2]])
972
    >>> np.random.seed(0)
973
    >>> pim = mdptoolbox.mdp.QLearning(P, R, 0.9)
Steven Cordwell's avatar
Steven Cordwell committed
974
    >>> ql.Q
975
976
    array([[ 39.933691  ,  43.17543338],
           [ 36.94394224,  35.42568056]])
Steven Cordwell's avatar
Steven Cordwell committed
977
    >>> ql.V
978
    (43.17543338090149, 36.943942243204454)
Steven Cordwell's avatar
Steven Cordwell committed
979
    >>> ql.policy
980
    (1, 0)
981
    
Steven Cordwell's avatar
Steven Cordwell committed
982
983
984
    """
    
    def __init__(self, transitions, reward, discount, n_iter=10000):
985
        # Initialise a Q-learning MDP.
Steven Cordwell's avatar
Steven Cordwell committed
986
        
987
988
989
        # The following check won't be done in MDP()'s initialisation, so let's
        # do it here
        if (n_iter < 10000):
Steven Cordwell's avatar