## Problem Set 3

Assigned: Oct. 29
Due: Nov. 12

### Problem 1

Consider the following scenario. There is a blocks world, with two blocks A and B on a table. The actions are as usual, except that any attempt at an action has a 1/3 probability of failing. If an attempt fails, then the position of the blocks remains the same.

You are playing the following game. Initially, block B is on block A. At each step, you have the option of attempting to move the blocks, or of quitting the game. Each attempt to move the blocks costs \$1. When you quit, if B is on A, then you collect 0; if both blocks are on the table, then you collect \$1; if A is on B, then you collect \$5. (Assume that utility is the same as dollar amount, which is valid for small sums like these.)

A. Explain how this can be construed as a Markov Decision Problem. What is the optimal policy? What is the value of the starting state?

B. We now consider a modification of the above game. Suppose that you do not find out whether an action has succeeded or failed. An attempt at an impossible action always fails.

• i. What is the expected value of the following plan: put(B,table), put(A,B)?
• ii. What is the expected value of the following plan: put(B,table), put(B,table), put(A,B), put(A,B)?

C. Suppose that, after each action, you are given a report whether the action succeeded or failed, but that this report has only a 2/3 chance of being correct. (This is a partially observable Markov decision problem (POMDP).) What is the value of the following plan:

```repeat put(B,table) until report success;
repeat put(A,B) until report success;
quit.
```
(If you are having trouble summing the infinite series involved, then it will suffice to estimate the value to 3 decimal places.)

### Problem 2

(For each part of the problem below, you should give a proof of your answer. If your answer is a range, rather than a single value, then you should prove, both that no value outside the range is possible, and that every value in the range is possible.)

A. Suppose that Prob(A|B) = 0.9 and Prob(B|C) = 0.9. What is the range of possible values of Prob(A|C),

• i. in the absence of any independence assumptions?
• ii. assuming that A and C are independent absolutely?
• iii. assuming that A is independent of C given B?

B. Suppose that Prob(A|C) = 0.9 and Prob(B|C) = 0.9. What is the range of possible values of Prob(A^B|C),

• i. in the absence of any independence assumptions?
• ii. assuming that A and B are independent absolutely?
• iii. assuming that A is independent of B given C?