代做Machine Learning Theory (CSC 431/531) Problem Set 4代写C/C++程序

Machine Learning Theory (CSC 431/531)

Problem Set 4

Due on Friday April 4th, 11:59pm

Instructions:

• You must write up your solutions individually.

• You may have high-level discussions with 1 other student registered in the course.  If you discuss problems with another student, include at the top of your submission:  their name, V#, and the problems discussed.

• You may not use Large Language Models to work on these problems.  Also, please do not “hunt for solutions” by trying to find solutions online or in textbooks.  Doing so defeats the purpose of working on the problems. Instead, please come to office hours if you are stuck on a problem (or email me).

• Your must type up your solutions and are encouraged to use LaTeX to do this.  For any problems where you only have a partial solution, be clear about any parts of your solution for which you have low confidence.

•  Please be sure to submit your solutions via Brightspace by the due date/time indicated above. This is a hard deadline.

Questions:

1. In this question, we consider a zero-sum game parameterized by a game matrix. In particular, we look at a variant of a game called matching pennies.

In our variant of this game, each player has a penny.  Player I first picks a strategy to turn their penny to either Heads or Tails.  Player II, with knowledge  of Player I’s strategy, then turns their own penny to either Heads or Tails. Note that both players can use mixed strategies.

If the two pennies match (i.e. are turned to the same side), then Player I wins (“suffering” a loss of -1) and Player II loses (suffering a loss of +1).  If the pennies are turned to opposite sides, then Player I loses (suffering a loss of +2) and Player II wins (“suffering” a loss of -2). The losses of Player I are specified by the game matrix M below:

The loss of Player II is always the negation of the loss of Player I (so this is a zero-sum game).

Since each player can randomize over their actions, we use p to denote the probability that Player I selects Heads, and we use q to denote the probability that Player II selects Heads.

(a) If Player I plays mixed strategy p ∈ [0, 1], what is the best response of Player II? That is, as a function of p, what choice of q*  should Player II make so as to satisfy

(b) Next, assuming that Player II plays a best response to Player I, what is Player I’s optimal strategy? That is, find p*  ∈ [0, 1] such that

2.  Consider Theorem 1 from Lectures 15 and 16 (link).  This problem is about showing an improved regret bound when there are many experts that have small cumulative loss.  Adapt the proof of Theorem 1 to get the following regret bound:

where KL  is the cardinality of the set {j ∈ [K] : Lj,T  ≤ L}.

You only need to show the parts of the proof that need to change.  It is possible to give a short, completely correct answer.