This assignment is designed for you to practice classical bandit algorithms in a simulated recommendation system, whose objects all live in the same $\mathbb{R}^d$:

  • Article: each article is a feature vector $\mathbf{x}$.
  • User: each user is a hidden preference vector $\boldsymbol{\theta}$.
  • Reward: showing article $\mathbf{x}$ to user $\boldsymbol{\theta}$ yields
\[\text{reward} = \boldsymbol{\theta}^\top \mathbf{x} + \varepsilon, \qquad \varepsilon \sim \mathcal{N}(0, \sigma^2),\]

Each step, a random subset of articles is offered. Your algorithm picks one, observes the reward, and updates its beliefs. Your algorithm’s task is to act well under partial knowledge.

  • Part 1: Multi-armed bandit (40 points) — the algorithm ignores $\mathbf{x}$ and treats each article as an independent arm.
  • Part 2: Contextual linear bandit (55 points) — the algorithm uses $\mathbf{x}$ to estimate $\boldsymbol{\theta}$, so a reward on one article also tells it about similar articles.
  • Part 3: Case study (5 points) - explore an industrial-level bandit-based recommendation system.

For code-level details, please refer to the README.md in your starter code. The report must be in PDF format, and simply name your submission by your student ID dash assignment1, e.g., “2026000000-assignment1.PDF”.

Part 1: Multi-armed Bandit Problem (40 points)

1.1 Implement Multi-armed Bandit Algorithms

In the multi-armed bandit, rewards of different arms are independent. The learner sees only the arm index. Implement the following algorithms for the multi-armed bandit with Gaussian reward noise:

  • Upper Confidence Bound (UCB)
  • Thompson Sampling (TS)
  • Perturbed-history Exploration (PHE)

See eps_greedy.py for a complete example. In this part, the algorithms should use only article id, not feature vectors.

1.2 Comparison in Different Environment Settings

Playing with different hyper-parameter settings of the simulation environment:

  • Experiment with different number of articles K and see how it influences the performance
  • Experiment with different amount of Gaussian noise in the reward and see how it influences the performance

Deliverables:

  • (15 points) Write the three algorithms you use, and clearly list the procedure for each algorithm. Explicitly list the equations for computing scores.
  • (15 points) Copy and paste the key components of your implementation: arm selection and parameter update.
  • (10 points) Include the plots and summarize your findings for the experiments you conduct for Section 1.2. You should also list the values of other environment parameters you set for the experiments.

Part 2: Contextual Linear Bandit Problem (55 points + 10 bonus points)

Now, each user has an unobservable linear parameter $\boldsymbol{\theta}$. In each time step, the algorithm observes the feature vectors $\mathbf{x}$ of the articles, select one and observe the reward. The algorithm maintain sufficient statistics and construct linear regression estimator for the unknown parameter.

2.1 Implement Contextual Linear Bandit Algorithms

For this section, we are going to see how the three principles mentioned above work in the linear bandit problem.

  • LinUCB
  • LinTS
  • LinPHE

See eps_greedy_linear.py for example of how to implement the linear bandit algorithm. Remember that in this environment the algorithm can use article’s feature vector.

2.2 Comparison in Different Environment Settings

Playing with different hyper-parameter settings of the simulation environment:

  • Experiment with different dimensions of feature vectors and see how it influences the performance
  • Experiment with different amount of Gaussian noise in the reward (standard deviation: NoiseScale) and see how it influences the performance
  • Experiment with different size of action set and see how it influences the performance, e.g. learner observes the whole set of articles as well as different sizes of the subsets of articles.

2.3 Influence of the Shape of Action Set

In this section, we investigate when / why linear bandit algorithms (algorithms that utilize feature vectors of articles) has advantage over multi-armed bandit (algorithms that only knows index of articles).

First, we need to set the hyper-parameters of the simulation environment to make fair comparison:

  • pool_article_size = None
  • n_articles = context_dimension = K

Then run the algorithms under: 1) actionset = “basis_vector” 2) actionset = “random”

For linear bandit algorithms, the accumulated regret under which setting is smaller? And why? (Hint: what is the relationship between the linear bandit setting where feature vectors are all basis vectors and the multi-armed bandit?) Can you explain using the regret upper bound results of the bandit algorithm.

Try different K and see how the discrepancy of the performance under two settings changes.

Deliverables:

  • (15 points) Write the three algorithms you use, and clearly list the procedure for each.
  • (15 points) Copy and paste the key components of your implementation: arm selection and parameter update.
  • (15 points) Include the plots and summarize your findings for the experiments you conduct for Section 1.2. You should also list the values of other environment parameters you set for the experiments.
  • (10 points) Include the plots and summarize your findings for the experiments you conduct for Section 2.3.

Part 3: Case Study: Mab2Rec (5 points)

Read the Mab2Rec library, an open-source framework for building bandit-based recommender systems. Study this project, and briefly answer the following questions:

  • Which bandit algorithms are included in this project?
  • How does its problem formulation relate to ours? In particular:
    • How does its notion of item, user features, and response map onto our articles, feature vectors, and reward?
    • Compare its linear contextual formulation with our setting.
    • How does its scoring differ from our Gaussian linear reward? What is the potential influence?s

We encourage you to use AI-assisted tools to explore the Mab2Rec project. If you are using one, please specify the agent harness and backbone LLM.

References

You may find the following materials useful:

Part 1 — MAB

Part 2 — Linear Bandit