Homework -
Q1. Consider a discounted cost problem with the following parameters:
-State space: {1, 2},
-Action spaces: U(1) = {1, 2}, U(2) = 1.
-Rewards: r(1; 1) = 5, r(1, 2) = 10, r(2, 1) = 1.
-Transition probabilities: P(u = 1) =
; P(u = 2) = 
(* is undefined)
-Discount factor β = 0:9
Find a policy that maximizes infinite horizon discounted reward.
Q2. A target is randomly moving among I locations according to a Markov chain with transition matrix P. An agent wants to follow this target. At each time, the agent sees the target location and its own location. It then decides to move to a new location.
(i) If the target is at location i and the agent at location j at the beginning of time instant t, the agent incurs a cost of c(i, j).
(ii) If the agent's location at the beginning of time instant t is j and it decides to move to k, it incurs a moving cost of d(j, k).
Formulate the agent's problem as a discounted cost MDP. Use Matlab (or another software) to find the optimal policy with the following values:
I = 4;
β = 0.95
Q3. A person has an umbrella that she takes from home to office and vice versa. There is a probability p of rain at the time she leaves home or office independently of earlier weather. If the umbrella is in the place where she is and it rains, she takes the umbrella to go to the other place (and this involves no cost). If there is no umbrella, and it rains, there is a cost W for getting wet. If the umbrella is in the place where she is but it does not rain, she may take the umbrella to the other place (and this involves an inconvenience cost V) or she may leave the umbrella behind (which involves no cost). Costs are discounted at a factor β, 0 < β < 1.
(a) Formulate this as an infinite horizon discounted cost problem. Identify the state and decision spaces. (Note that the decision spaces can be different for different states.)
(b) Write the fixed point equation for the value function and characterize the optimal strategy.
Q4. Show that the minimum cost is the solution of linear program:
Maximize J*
Subject to
J* + w(i) ≤ c(i, u) + j=1∑I Pij(u)w(j), 1 ≤ i ≤ I, u ∈ U.