## Artificial Intelligence: Problem Set 5

Assigned: Mar. 28
Due: April 11

### Problem 1

Consider the following game: On each turn, you pay an ante of \$1, and you roll a die. If it comes up heads, you get back \$10 and the game is over (you do not also get back your ante in addition). If the coin comes up tails, you may take another turn. You can quit the game at any time.
• A. Show how this game can be construed as a Markov decision process. What is the expected value of the game?
• B. Consider a modified version of the game, in which the ante is \$1 on the first turn, \$2 on the second, and continues to increase by \$1 each move. Explain why this does not give a separable utility function on histories.
• C. Give an argument to show that, if the ante increases monotonically over time, then the optimal strategy is to continue playing until the ante reaches \$5, and then stop.
• D. Assuming that the player uses the strategy in C for the game in B, what is the expected value of the game?
• E. Suppose that the ante starts at \$6 and decreases by \$1 each turn until it reaches 0, and then stays 0. What is the value of the game at the beginning?

### Problem 2

Suppose that we are trying to learn a relation R(a,b,c,d) over four integer-valued parameters a,b,c,d. We conjecture that R is either an inequality of one of the forms "X > Y", "X > = Y" or "X = Y", or R is the conjunction of two such inequalities. No more than two inequalities will be considered. Thus, some of the elements of the version space include
d > = b.
a = c & d > c.
b > d & c > = a.
and so on. We will also include in our version space the universal relation, satisfied by all quadruples, and the empty relation, satisfied by no quadruples.

Describe what will happen if the candidate elimination algorithm is applied to this problem and the following examples are encountered, in succession. That is, you should show the successive values of the sets S and G as each new example is encountered.

R(3,1,4,2) is satisfied.
R(2,2,1,3) is not satisfied.
R(1,3,4,4) is satisfied.