RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search

• URL: http://arxiv.org/abs/2605.18004v1
• Date: Mon, 18 May 2026 07:57:26 GMT
• Title: RL4RLA: Teaching ML to Discover Randomized Linear Algebra Algorithms Through Curriculum Design and Graph-Based Search
• Abstract summary: We present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms.<n>Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations.<n>We demonstrate that RL4RLA rediscovers state-of-the-art methods, including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch.
• Score: 18.388661543349
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Randomized linear algebra (RLA) algorithms are a modern class of numerical linear algebra techniques that play an essential role in scientific computing and machine learning, with broad and growing adoption. However, their discovery remains mostly a manual process that requires deep expert knowledge and inspiration. While Reinforcement Learning (RL) offers a pathway to automation, standard approaches struggle with sparse reward landscapes and vast search spaces inherent to high-performing RLA algorithms. In this paper, we present RL4RLA, a general RL framework that automates the discovery of interpretable, symbolic RLA algorithms. Unlike black-box approaches, our method builds explicit algorithms from basic linear algebra primitives, ensuring verifiable and implementable representations. To enable efficient discovery, we introduce: (1) a numerical curriculum that progressively increments problem difficulty to encode inductive bias specific to the RLA domain; (2) Monte Carlo Graph Search, which optimizes exploration by identifying and merging equivalent partial algorithms. We demonstrate that RL4RLA rediscovers state-of-the-art methods, including sketch-and-precondition solvers, Randomized Kaczmarz, and Newton Sketch, and can be targeted to produce algorithms optimized for specific trade-offs between accuracy, speed, and stability. Code is available at https://github.com/Tim-Xiong/RL4RLA.

Related papers

• Replicable Reinforcement Learning with Linear Function Approximation [21.370247743205056]
  We introduce two efficient algorithms for replicable random design regression and uncentered covariance estimation.<n>We then leverage these tools to provide the first provably efficient RL algorithms for linear Markov decision processes.<n>We evaluate our algorithms experimentally and show how they can inspire more consistent neural policies.
  arXiv  Detail & Related papers  (2025-09-10T14:56:09Z)
• How Should We Meta-Learn Reinforcement Learning Algorithms? [69.12853522797188]
  We carry out an empirical comparison of the different approaches when applied to a range of meta-learned algorithms.<n>In addition to meta-train and meta-test performance, we also investigate factors including the interpretability, sample cost and train time.<n>We propose several guidelines for meta-learning new RL algorithms which will help ensure that future learned algorithms are as performant as possible.
  arXiv  Detail & Related papers  (2025-07-23T16:31:38Z)
• Discovering Algorithms with Computational Language Processing [0.7062238472483737]
  We present a framework automating algorithm discovery by conceptualizing them as sequences of operations, represented as tokens.<n>These computational tokens are chained using a grammar, enabling the formation of increasingly sophisticated procedures.<n>Our ensemble Monte Carlo tree search (MCTS) guided by reinforcement learning (RL) explores token chaining and drives the creation of new tokens.
  arXiv  Detail & Related papers  (2025-07-03T21:45:17Z)
• Recent and Upcoming Developments in Randomized Numerical Linear Algebra for Machine Learning [49.0767291348921]
  Randomized Numerical Linear Algebra (RandNLA) is an area which uses randomness to develop improved algorithms for ubiquitous matrix problems. This article provides a self-contained overview of RandNLA, in light of these developments.
  arXiv  Detail & Related papers  (2024-06-17T02:30:55Z)
• CoLA: Exploiting Compositional Structure for Automatic and Efficient Numerical Linear Algebra [62.37017125812101]
  We propose a simple but general framework for large-scale linear algebra problems in machine learning, named CoLA. By combining a linear operator abstraction with compositional dispatch rules, CoLA automatically constructs memory and runtime efficient numerical algorithms. We showcase its efficacy across a broad range of applications, including partial differential equations, Gaussian processes, equivariant model construction, and unsupervised learning.
  arXiv  Detail & Related papers  (2023-09-06T14:59:38Z)
• Reward-Machine-Guided, Self-Paced Reinforcement Learning [30.42334205249944]
  We develop a self-paced reinforcement learning algorithm guided by reward machines. The proposed algorithm achieves optimal behavior reliably even in cases in which existing baselines cannot make any meaningful progress. It also decreases the curriculum length and reduces the variance in the curriculum generation process by up to one-fourth and four orders of magnitude, respectively.
  arXiv  Detail & Related papers  (2023-05-25T22:13:37Z)
• Reinforcement Learning for Branch-and-Bound Optimisation using Retrospective Trajectories [72.15369769265398]
  Machine learning has emerged as a promising paradigm for branching. We propose retro branching; a simple yet effective approach to RL for branching. We outperform the current state-of-the-art RL branching algorithm by 3-5x and come within 20% of the best IL method's performance on MILPs with 500 constraints and 1000 variables.
  arXiv  Detail & Related papers  (2022-05-28T06:08:07Z)
• Jump-Start Reinforcement Learning [68.82380421479675]
  We present a meta algorithm that can use offline data, demonstrations, or a pre-existing policy to initialize an RL policy. In particular, we propose Jump-Start Reinforcement Learning (JSRL), an algorithm that employs two policies to solve tasks. We show via experiments that JSRL is able to significantly outperform existing imitation and reinforcement learning algorithms.
  arXiv  Detail & Related papers  (2022-04-05T17:25:22Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  We propose a method for meta-learning reinforcement learning algorithms. The learned algorithms are domain-agnostic and can generalize to new environments not seen during training. We highlight two learned algorithms which obtain good generalization performance over other classical control tasks, gridworld type tasks, and Atari games.
  arXiv  Detail & Related papers  (2021-01-08T18:55:07Z)
• Discovering Reinforcement Learning Algorithms [53.72358280495428]
  Reinforcement learning algorithms update an agent's parameters according to one of several possible rules. This paper introduces a new meta-learning approach that discovers an entire update rule. It includes both 'what to predict' (e.g. value functions) and 'how to learn from it' by interacting with a set of environments.
  arXiv  Detail & Related papers  (2020-07-17T07:38:39Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.