The system parameters are ${}_d,D,S_{\text{m}\text{a}\text{x}},,{}_1,{}_2,{}_3,$ and ${}_k.$ Some of these parameters capture the probability distributions governing state transition and reward. You will assume that these parameters are known for all the deliverables below.

Deliverables:

$(10$ marks$)$ Implement iterative policy evaluation to find the value function of a greedy policy for problem $1.$ Greedy policy is the one that minimizes the immediate average reward. You MUST implement this code in the Python script policy$\_$evaluation.py that is provided to you. The function MUST return the value function for the greedy policy. The only thing that you should include in report.pdf for this part is an equation that describes the greedy policy.

${?}^1$ I don't think that the hardcoded rule is sub$-$optimal. You will get $5$ buffer marks $($out of $100$ marks for this entire course$)$ if you manage to RIGOROUSLY prove it$.$ I have not taught you these kind of proofs, you have to find it out yourself. Alternately, you can also disprove my claim and get these $5$ buffer marks.

$(15$ marks$)$ Implement value iteration to solve the Bellman optimality equation for problem $3.$ You MUST implement this code in the Python script value$\_$iteration.py that is provided to you. The function MUST return the optimal value function and the optimal policy. You MUST NOT include anything in report.pdf for this part. It is crucial that your code can run for any value of $,$ even $=0(=0$ means non$-$deferrable demands like in problem $1).$

$(15$ marks$)$ Implement policy iteration to solve the Bellman optimality equation for problem $3.$ You MUST implement this code in the Python script policy$\_$iteration.py that is provided to you. The function MUST return the optimal value function and the optimal policy. You MUST NOT include anything in report.pdf for this part. It is crucial that your code can run for any value of $,$ even $=0(=0$ means non$-$deferrable demands like in problem $1).$

Read these points before attempting the above deliverables:

Default system parameters: The following are the default values of the involved parameters: $D=5,=4,S_{\text{m}\text{a}\text{x}}=15,{}_1=10,{}_2=1,{}_3=0\mathrm{.}2,{}_k=0\mathrm{.}3$kAAk. The default value of discount factor $=0\mathrm{.}95.$ In the pseudocode of iterative policy evaluation, value iteration, and policy iteration, there was a convergence threshold $$ in the lecture slides $($this $$ is different from ${}_1,{}_2,$ and ${}_3).$ Set this convergence threshold as $2.$ An additional convergence parameter is $K_{\text{m}\text{i}\text{n}},$ the minimum number of iterations for iterative policy evaluation, value iteration, and policy evaluation of policy iteration. Set $K_{\text{m}\text{i}\text{n}}=10.$ These default value MUST be used for testing your code and doing analysis in the next section unless mentioned otherwise. NOTE: Your code must run for any values and not just the default ones.

You are provided a Python script

Assignment$2$Tools.py that contains a function prob$\_$vector$\_$generator$().$ This function can be used to generate a probability distribution, ${}_d,$ that has a pre$-$specified mean and standard deviation. The instruction to use this function is there in policy$\_$evaluation.py$,$ value$\_$iteration.py$,$ and policy$\_$iteration.py$.$

For a given set of system parameters, the optimal value function obtained using value and policy iteration should almost be the same. Otherwise, there is something wrong with your code.

While coding the Q $-$function, you may want to use the broadcasting operation of Numpy to speed your computation. The following are the run times for default parameters in my office laptop:

policy$\_$evaluation.py produces results in like $5$ seconds.

The run time of value$\_$iteration.py and policy$\_$iteration.py is less than $32$ minutes. One of them runs around three times faster than the other $($not going to tell which one$).$

Must account for action space: You must take into consideration that different states may have different action space. This means a few things. First, while implementing value$/$policy iteration, the maxima$/$minima should be over the action space corresponding to the state. Second, for policy iteration, the policy can be initialized to any arbitrary value in the action space corresponding to the state.