CPSC422 Spring 2012
Assignment 2

CPSC422 Spring 2012
Assignment 2

Due: 10:00am, Wednesday 18 January 2012.

You are encouraged to discuss this assignment and collaborate with your classmates, as long as (a) you list the people with whom you discussed the assignment and (b) you give your own answers to the questions. Feel free to ask questions on the Vista bulletin board.

Question 1

Explain how Q-learning fits in with the agent architecture of Section 2.2.1 of the textbook. Suppose that the Q-learning agent has discount factor $\gamma $, a step size of $\alpha $, and is carrying out an $\epsilon $-greedy exploration strategy.

What are the percepts of an agent?

What are the components of the belief state of the Q-learning agent?

What is the command function of the Q-learning agent?

What is the belief-state transition function of the Q-learning agent?

Question 2

Compare the different parameter settings for the game of Example 11.8 of the textbook, as at http://artint.info/demos/rl/sGameQ.html. In particular compare the following situations:

$\alpha $ varies, and the $Q$-values are initialized to 0.0.

$\alpha $ varies, and the $Q$-values are initialized to 5.0.

$\alpha $ is fixed to 0.1, and the $Q$-values are initialized to 0.0.

$\alpha $ is fixed to 0.1, and the $Q$-values are initialized to 5.0.

Some other parameter settings.

For each of these, carry out multiple runs and compare the distributions of minimum values, zero crossing, the asymptotic slope for the policy that includes exploration, and the asymptotic slope for the policy that does not include exploration. To do the last task, after the algorithm has converged, set the exploitation parameter to 100% and run a large number of additional steps.

Question 3

Consider four different ways to derive the value of $\alpha _ k$ from $k$ in Q-learning (note that for Q-learning with varying $\alpha _ k$, there must be a different count $k$ for each state–action pair).

Let $\alpha _ k = 1/k$.

Let $\alpha _ k = 10/(9+k)$.

Let $\alpha _ k = 0.1$.

Let $\alpha _ k = 0.1$ for the first 10,000 steps, $\alpha _ k = 0.01$ for the next 10,000 steps, $\alpha _ k = 0.001$ for the next 10,000 steps, $\alpha _ k = 0.0001$ for the next 10,000 steps, and so on.

Which of these will converge to the true $Q$-value in theory?

Which converges to the true $Q$-value in practice (i.e., in a reasonable number of steps)? Try it at least for the simple game at http://artint.info/demos/rl/sGameQ.html. Note that for the code, $\alpha $ is set in $dostep$ in $SGameQController.java$.

Which can adapt when the environment changes slowly?

Question 4

How long did this assignment take? What did you learn? Was it reasonable?

Mini-project suggestions

One way to understand the effect of different $\alpha $s in temporal difference learning is to plot the values and the estimates through time. What happens if the values change (e.g., in a step function)? What happens if the values keep rising? What happens if there is noise in the values? Plot some scenarios and explain to the class what you learned from doing this.

CPSC422 Spring 2012
Assignment 2