Multi-Task Representation Learning for Conservative Linear Bandits

Jiabin Lin, Shana MoothedatharXiv 2026 · arXiv

This paper introduces a new framework for Constrained Multi-Task Representation Learning (CMTRL) in linear bandits. It tackles the challenge of learning a shared, low-dimensional structure across multiple tasks while ensuring that every action taken by the learning agent satisfies strict safety or performance constraints.

TL;DR

The authors propose Safe-AltGDmin, a novel algorithm that enables multiple bandit tasks to share a low-rank representation while guaranteeing "conservative" behavior—meaning the agent never performs significantly worse than a known baseline policy. The framework achieves sublinear regret and significantly better sample efficiency than solving tasks independently, all while maintaining zero safety violations.

What Problem Does This Paper Address?

In many real-world applications of machine learning—like autonomous driving, medical trials, or power grid management—exploration is risky. Standard bandit algorithms learn by trial and error, but in these "safety-critical" domains, a bad "trial" can be catastrophic. Conservative bandits solve this by requiring that the reward for any chosen action stays above a certain percentage of a known baseline policy's reward.

Simultaneously, we often deal with many related tasks (e.g., recommending movies to thousands of different users). Multi-Task Representation Learning (MTRL) assumes these tasks share a common underlying structure (a low-rank feature matrix). While MTRL is great for reducing the amount of data needed to learn, combining it with safety constraints is mathematically difficult because the resulting optimization problem is non-convex and the safety requirements must be met at every single step of the learning process.

Methods

The authors introduce the Safe-AltGDmin algorithm, which operates in epochs using a "doubling schedule." Its core components include:

  1. Safe Exploration: In the initial phase, the algorithm doesn't just follow the baseline. It uses a "conservative feature vector" that mixes the baseline action with a small amount of random Gaussian noise. A carefully tuned parameter, $\rho$, balances the need to explore new information with the requirement to stay safe.
  2. Spectral Initialization: Because the underlying optimization is non-convex, the algorithm needs a good starting point. The authors use a truncated Singular Value Decomposition (SVD) strategy to initialize the shared feature matrix.
  3. Alternating Minimization (AltGDmin): The algorithm refines its model by alternating between two steps:
  4. Gradient Descent (GD): Updating the shared low-rank feature matrix ($B$).
  5. Minimization: Updating the task-specific weight vectors ($w_t$) for each task.
  6. Greedy Exploration with Safety Bounds: In later epochs, the agent uses its learned model to pick the best possible actions. Crucially, the authors provide theoretical bounds on the estimation error, allowing the agent to prove that its "greedy" choices will still satisfy the safety constraints.

Datasets

The researchers evaluated their algorithm using two primary sources:

  • Synthetic Data: A controlled environment with 100 tasks in a 100-dimensional space, sharing a rank-2 representation. This allowed for precise measurement of estimation error and regret.
  • Movielens-100K: A real-world dataset of movie ratings. They used Non-negative Matrix Factorization (NMF) to create a "ground truth" low-rank structure and clustered users into tasks to simulate a multi-task recommendation environment.

Key Insights and Ideas

  • Efficiency through Sharing: By assuming a low-rank structure ($r \ll d$), the regret scales with the low-rank dimension $r$ rather than the full dimension $d$. This is a massive win for high-dimensional problems.
  • The Safety-Exploration Trade-off: The parameter $\rho$ is the "knob" for safety. The authors provide a specific upper bound for $\rho$ that guarantees safety even when the model is still being learned.
  • Sublinear Regret: The paper proves that the cumulative regret grows sublinearly with the number of tasks $T$ and samples $N$. As shown in Figure 2, the regret curve flattens over time as the model improves.
Figure 2: Cumulative regret vs. number of epochs.
  • Non-Convexity is Manageable: Unlike previous methods that use "trace-norm" convex relaxations (which can be computationally heavy and less accurate), this work shows that alternating gradient descent with good initialization is both faster and more effective.

Key Results

The authors compared Safe-AltGDmin against several benchmarks, including trace-norm relaxation and Method-of-Moments (MoM). The results, summarized in Table I and Figure 1, show:

  • Zero Violations: While trace-norm and MoM methods frequently violated safety constraints to achieve lower regret, Safe-AltGDmin (and a naive Thompson Sampling baseline) maintained zero violations across all experiments.
  • Superior Regret: Safe-AltGDmin achieved significantly lower cumulative regret than the safe Thompson Sampling baseline, proving that leveraging the shared multi-task structure is highly effective.
  • Estimation Accuracy: The algorithm's error in estimating the shared representation decreased exponentially, outperforming all other tested methods in accuracy.
Table I: Table comparing technical contributions of existing work versus ours.

Limitations and Future Work

  • Gaussian Assumptions: The current theoretical analysis assumes that features follow a standard Gaussian distribution. The authors noted that relaxing this to non-zero mean or non-Gaussian distributions is a key goal for future work.
  • Known Baseline: The framework relies on the existence of a known baseline policy. In some very new domains, such a baseline might not exist.
  • Linearity: The model is strictly linear. Extending these safety and multi-task guarantees to non-linear models (like neural networks) remains a significant open challenge in the field.

Summary updated

Abstract

This paper presents the Constrained Multi-Task Representation Learning (CMTRL) framework for linear bandits. We consider T linear bandit tasks in a d dimensional space, which share a common low-dimensional representation of dimension r, where r is much smaller than the minimum of d and T. Furthermore, tasks are constrained so that only actions meeting specific safety or performance requirements are allowed, referred to as conservative (safe) bandits. We introduce a novel algorithm, Safe-Alternating projected Gradient Descent and minimization (Safe-AltGDmin), to recover a low-rank feature matrix while satisfying the given constraints. Building on this algorithm, we propose a multi-task representation learning framework for conservative linear bandits and establish theoretical guarantees for its regret and sample complexity bounds. We presented experiments and compared the performance of our algorithm with benchmark algorithms.
BibTeX
@misc{lin2026multi,
  author = {Jiabin Lin and Shana Moothedath},
  title = {{Multi-Task Representation Learning for Conservative Linear Bandits}},
  year = {2026},
  eprint = {2605.12176},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.12176},
}

Loading related content...

Figure