Browse Groups

• Hello mates, I ve been testing my java code for the algorithm POLICY-ITERATION (chapter 17). It solves the Simplified Bellman Equations (SBE) for the MDP
Message 1 of 1 , Aug 13, 2006
View Source
Hello mates,
I've been testing my java code for the algorithm POLICY-ITERATION (chapter 17).
It solves the Simplified Bellman Equations (SBE) for the MDP example of the
book. However, because the first policy is a random one, there are situations
where the SBE are not solvable. I wonder if it is a known issue and if there is
an easy workaround for it. An example follows.

The discount is 1. The random first policy is:

{41=NORTH, 32=NORTH, 23=WEST, 21=NORTH, 12=NORTH, 31=SOUTH, 13=WEST, 33=EAST, 11=SOUTH}

Then the linear equations (Bellman Equations) in Matrix form are:

4,1 3,2 2,3 2,1 1,2 3,1 1,3 3,3 1,1
+ -------------------------------------------------------------------------------
|
4,1 | -9/10 0 0 0 0 1/10 0 0 0 21/25
2,3 | 0 0 -4/5 0 0 0 4/5 0 0 1/25
3,2 | 0 -9/10 0 0 0 0 0 4/5 0 7/50
1,2 | 0 0 0 0 -4/5 0 4/5 0 0 1/25
2,1 | 0 0 0 -1/5 0 1/10 0 0 1/10 1/25
1,3 | 0 0 0 0 1/10 0 -1/10 0 0 1/25
3,1 | 1/10 0 0 1/10 0 -1/5 0 0 0 1/25
3,3 | 0 1/10 0 0 0 0 0 -9/10 0 -19/25
1,1 | 0 0 0 1/10 0 0 0 0 -1/10 1/25

The next code in Maxima (a free mathematical software) shows that the linear
system is not solvable (because the ranks are different):

----------------- Maxima --------------------------

a:matrix([-9/10,0,0,0,0,1/10,0,0,0], [0,0,-4/5,0,0,0,4/5,0,0], [0,-9/10,0,0,0,0,0,4/5,0], [0,0,0,0,-4/5,0,4/5,0,0], [0,0,0,-1/5,0,1/10,0,0,1/10], [0,0,0,0,1/10,0,-1/10,0,0], [1/10,0,0,1/10,0,-1/5,0,0,0], [0,1/10,0,0,0,0,0,-9/10,0], [0,0,0,1/10,0,0,0,0,-1/10]);

/* returns 8: */
rank(a);

b:[21/25,1/25,7/50,1/25,1/25,1/25,1/25,-19/25,1/25];

/* returns 9: */
rank(ae);

-----------------------------------------------------

--
Ivan F. Villanueva B.
A.I. library: http://www.artificialidea.com
<<< The European Patent Litigation Agreement (EPLA) >>>
<<< will bring Software patents by the backdoor >>>
<<< http://www.no-lobbyists-as-such.com/florian-mueller-blog/epla/ >>>
<<< http://wiki.ffii.de/EplaEn >>>
Your message has been successfully submitted and would be delivered to recipients shortly.
• Changes have not been saved
Press OK to abandon changes or Cancel to continue editing
• Your browser is not supported
Kindly note that Groups does not support 7.0 or earlier versions of Internet Explorer. We recommend upgrading to the latest Internet Explorer, Google Chrome, or Firefox. If you are using IE 9 or later, make sure you turn off Compatibility View.