## 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.