1.  Consider we are developing a security system against three potential types of attackers.  The payoff for each type is listed as a 2x2 normal form game, where the attacker is the column player, as follows:

Reward ri,j  is the reward the Row player (agent A) receives when it takes action ai  and Column player (agent B) takes action aj. Similarly, ri(/),j  corresponds to the reward for the column player (agent B) when A takes ai  and B takes aj. We will represent that table in Python as a list of lists, where each inner list corresponds to a row, as follows:  [[(r0,0 , r0(/) ,0 ), (r0,1 , r0(/) ,1 )], [(r1,0 , r 1(/) ,0 ), (r1,1 , r 1(/) ,1 )]].

(a) Write in Python a function bayesianNashEquilibria(rewardsB1, rewardsB2,

rewardsB3, probs), which receives a normal form game for each potential type (rewardsB1, rewardsB2, rewardsB3, respectively), and a correspond- ing probability for each type.  That is, probs = [p1 , p2 , p3], where pi  is the probability of the column player being of type Bi. The function returns a list of tuples, where each tuple is a pair of actions for each player if that pair is a Nash Equilibria of the game. The actions in each tuple will be represented as strings.  For instance, [(✬0✬, ✬110✬),(✬1✬, ✬101✬)] means that there are two Nash Equilibria in the game. One when row player plays a0 , and column player of type B1 and B2 play a1 , but B3 plays a0 . The second when row player plays a1 , and column player of type B1 and B3 play a1 , but B2 plays a0.  If the game has no pure strategy Nash Equilibria, then it returns an empty list:  [].

(b) Write in Python a function pureStackelberg(rewardsB1, rewardsB2, rewardsB3, probs),

which follows the same representation as before. However, this time it returns the pure strategy Stackelberg equilibria of the game. As before, the function returns a list of tuples, where each tuple is a pair of actions for each player if that pair is a Stackelberg Equilibria of the game.

Since we are handling pure strategies, we will consider the weak form of the Stackelberg Equilibria, where the follower break ties against the leader. That is, if multiple actions give the same reward for the follower, we will assume the follower will take the one with the lowest reward for the leader.

If the game has no pure strategy Stackelberg Equilibria, then it returns an empty list:  [].  (10%)

2.  Consider the approach given in Paruchuri et al. (2008) to solve Stackelberg Games. In the DOBSS formulation given in Problem (4) in Paruchuri et al.  (2008), what is the purpose of the constraint 0 ≤ ╱a -    ieX Cijxi、≤ (1 - qj)M? Why does it achieve the desired purpose? Please explain in detail using your own words.  (5%)

3.  Consider the gridworld below, similar to the one covered in class. We assume an agent (starting at position (0, 1)) must pick-up a cup of coffee (in position (1, 0)), and bring it to an office (in position (3, 1)). The agent can move in four directions: N, W, E and S. The transition probability for any action is such that the agent moves with a 0.8 probability in the intended direction, and 0.1 probability to the right or left of the intended direction, similar to the example shown in the class. There is also a fire-place in the building at position (3 , 0), which would cause severe

physical damage to the agent if it reaches that position. Additionally, if the agent is carrying the cup of coffee, it may drop it with a 0.1 probability. The cup would break if it is dropped, and a new one would need to be collected at position (1 , 0). Note that the y-axis has value 0 in the first row, and 1 in the second row, in order to potentially simplify your implementation.  Additionally, we consider that the states where the agent reaches the fire place (with or without coffee), or reaches the office with coffee, are terminal states.

0

1 

0          1         2         3

Write in Python a function  collectCoffee(goal, fire, movement),  which solves this problem using value iteration.  goal is the reward given to the agent when arriving in the office with coffee, fire is the reward when the agent reaches the fire place (with or without coffee), and movement is the reward given at any other situation.  Note that depending on the rewards assigned, the agent would fail to solve the intended problem of delivering coffee. Assume a discount factor 0.95. If any ties happen when calculating max utilities in the algorithm, then one of the actions with maximum utility must be chosen uniformly randomly.

For the purposes of this exercise, we will print the policy to the screen, following the same order as the grid-world scenario.  We will use the following characters:  ‘N’, ‘S’, ‘E’, ‘W’, for “North”, “South”, “East”, and “West”, respectively. Additionally, we will denote with a “.” when no action is taken. That would happen in terminal states, or in states that would never occur.  You must also show what the robot would do with and without coffee. For example:

No  Coffee:

E  .  W  .

N  N  W  W

Coffee:

E  S  W  .

E  E  E  .

Note that the format of the output must be followed very strictly in order to match with the test cases. Please use the “Precheck” button on Moodle in order to verify your solution.  (15%)

4.  Consider the same situation as the previous question. This time, however, we will employ reinforcement learning approaches.  Hence, let’s assume that the agent is able to perform multiple runs over this problem.   In each run the agent starts at (0, 1). Each run terminates when the agent reaches the position (3 , 0) (with or without coffee) or (3, 1) with coffee. We also consider that each run is independent.

That is, although the agent would get physically damaged when reaching position (3, 0), it will be back to its normal condition in the next run starting at (0 , 1).

Write in Python a function collectCoffeeRL(goal, fire, movement), which solves this problem using the TD  Q-Learning algorithm.   Use the  epsilon-greedy al- gorithm for selecting actions, with ∈ = 0.1, and assume α = 0.1 and discount factor 0.95.   Additionally, consider  10000 runs.   The output will be printed on the screen, following the same format as in the previous question.  For the final output, consider that the agent would always maximize the Q values, instead of using epsilon-greedy.  That is, the printed output would represent a final policy learned after training.

As before, if any ties happen when calculating max Q values in the algorithm, then one of the actions with maximum Q value must be chosen uniformly randomly.

(15%)

5. Assume now the same situation as in the previous question, but we will use a logistic function to represent the Q tables, and perform one learning iteration after every action, similarly to as seen in class (but note that the machine learning model now is not a simple linear function).  That is, every time we perform an action a, from a state s, obtain reward r, and reach a state s/ , we will perform weight updates given the information < a, s, s/ , r >.  Similarly to what was seen in class, we are going to use a separate set of weights for each action. Note: The class slides shows the derivation for a linear function approximation. It has to be adapted to handle the logistic model.

Write in Python a function  collectCoffeeFARL(goal, fire, movement),  which solves the problem as described.  Use the ∈-greedy approach for selecting actions. Consider ∈ = 0.1, α = 0.1, and discount factor 0.95. Additionally, all weights must be initialised with 0s.  We will also consider 2000 runs for training.  As before, all ties must be broken uniformly randomly.  The printed output must follow the same format as in the previous questions.  (15%)

6. According to Mnih et al.   (2015), which modifications were made by DQN in comparison to the standard function approximation approach?  Why these mod- ifications led to better performance in reinforcement learning?  Please explain in detail, using your own words.  (5%)

7. Let’s consider now a multi-arm bandit problem.  We will use the code Arm.py attached, which has a class Arm with the following interface:

❼ Arm(mu, sigma):  Constructor.  Initialises an arm, which will be simulated

by a Gaussian with mean mu and standard deviation sigma. ❼ pull():  “pull” the arm, returning a reward between 0 and 1.

This code will be automatically added to the beginning of your code.

Write a class UCB1, following the UCB1 approach described in Auer et al. (2002). You must implement the following interface:

❼ UCB1(arms): Class constructor. Receives a list of arm objects in arms.

❼ play():  Play one of the arms in arms, chosen by following the UCB1 algo-

rithm. It returns the index of the arm that was chosen.

We will assume that the arms will be played in order when they are being played for the first time.   Afterwards,  any ties must be broken uniformly randomly.  (5%)

8.  Consider that we are running the UCT Monte Carlo Tree Search algorithm, as described in Section 3.3 of Browne et al.   (2012).  Assume that the search tree stored in memory is currently as follows:

States in bold represent states with children that were not yet expanded.  Every state has two possible actions, a0  and a1 .  a0  leads to the left child node, and a1 leads to the right child node. We assume a single-agent MDP with a deterministic transition function.  That is, given a state s and an action a, the next state will be a certain s/  with probability 1.  We also assume that when evaluating a new node for the first time we will run a “default policy”, which will simulate the MDP until a final state where we obtain a reward.  We assume no discount factor, and exploration term constant Cp = 0.9.

Let’s assume that previous simulation results were as follows, where 疋 corresponds to the last digit of your student ID:

Show in detail 3 iterations of the UCT algorithm.   One iteration consists of a complete simulation, starting from the root of the tree. You can assume your own rewards when reaching the final state in a simulation. You will need to attach files in your reply on Moodle, in order to show the updated tree at each step. You can either use the text input, and attach image files, or submit a pdf file with your reply.  (10%)

9.  Please describe the similarities and differences between: (i) the UCT algorithm in Kocsis and Szepesv´ari (2006);  (ii) the UCT algorithm in Section 3.3 of Browne et al.  (2012);  (iii) the MCTS algorithm in Silver et al.  (2016);  (iv) the MCTS algorithm in Silver et al.  (2017).  (10%)