Instance Selection for Dynamic Algorithm Configuration with Reinforcement Learning: Improving Generalization

📄 arXiv: 2407.13513v1 📥 PDF

作者: Carolin Benjamins, Gjorgjina Cenikj, Ana Nikolikj, Aditya Mohan, Tome Eftimov, Marius Lindauer

分类: cs.LG

发布日期: 2024-07-18

期刊: GECCO 2024

💡 一句话要点

提出基于强化学习动态算法配置的实例选择方法，提升泛化性能

🎯 匹配领域: 支柱二：RL算法与架构 (RL & Architecture)

关键词: 动态算法配置 强化学习 实例选择 泛化性能 元特征

📋 核心要点

  1. 现有动态算法配置方法在面对多样化实例时泛化能力不足，限制了强化学习智能体的应用。
  2. 通过选择具有代表性的训练实例子集，减少训练偏差，提升强化学习智能体的泛化性能。
  3. 实验结果表明，所提出的实例选择方法能够有效改进动态算法配置策略，尤其是在多样化的实例空间中。

📝 摘要（中文）

动态算法配置(DAC)旨在为不同的实例动态设置算法的超参数，而非仅关注单个任务。深度强化学习(RL)训练的智能体为此提供了一种解决方案。然而，这些智能体有限的泛化性能严重阻碍了其在DAC中的应用。本文假设训练实例中的潜在偏差限制了泛化能力。通过选择具有代表性的训练实例子集来克服过度表示，并在该子集上重新训练智能体，从而提高其泛化性能。为了构建子集选择的元特征，特别考虑了RL智能体的动态特性，计算了智能体与环境交互产生的动作和奖励轨迹上的时间序列特征。通过在DACBench标准基准库中的Sigmoid和CMA-ES基准上进行实证评估，讨论了本文选择技术与在整个实例集上训练相比的潜力。结果表明，实例选择在改进多样化实例空间的DAC策略方面是有效的。

🔬 方法详解

问题定义：动态算法配置(DAC)旨在为不同的问题实例动态地调整算法的超参数，以获得最佳性能。然而，现有的基于强化学习的DAC方法在面对新的、未见过的实例时，泛化能力较差。这是因为训练集中可能存在偏差，导致智能体过度拟合训练数据，无法很好地适应新的实例。

核心思路：本文的核心思路是通过实例选择来减少训练集中的偏差，从而提高强化学习智能体的泛化能力。具体来说，选择一个具有代表性的实例子集，该子集能够更好地反映整个实例空间的分布，然后在这个子集上训练智能体。这样可以避免智能体过度拟合训练集中的特定实例，从而提高其在未见过的实例上的性能。

技术框架：该方法主要包含以下几个步骤：1）使用初始的强化学习智能体与环境交互，收集每个实例的动作和奖励轨迹。2）基于这些轨迹，提取时间序列特征，作为实例的元特征。3）使用这些元特征，选择一个具有代表性的实例子集。4）使用选择的实例子集重新训练强化学习智能体。5）评估重新训练的智能体在未见过的实例上的性能。

关键创新：该方法的关键创新在于使用强化学习智能体与环境交互产生的动作和奖励轨迹来构建实例的元特征。这种方法能够更好地捕捉实例的动态特性，从而更准确地评估实例的代表性。与传统的静态元特征相比，这种动态元特征能够更好地反映强化学习智能体与环境的交互过程，从而更有效地选择具有代表性的实例子集。

关键设计：在元特征提取方面，使用了时间序列特征，例如均值、方差、自相关系数等，来描述动作和奖励轨迹的动态特性。在实例选择方面，可以使用各种聚类或采样方法来选择具有代表性的实例子集。具体的强化学习算法和网络结构可以根据具体的应用场景进行选择。损失函数通常是强化学习中的标准奖励最大化目标。

🖼️ 关键图片

fig_0
fig_1
fig_2

📊 实验亮点

在DACBench的Sigmoid和CMA-ES基准测试中，使用实例选择方法训练的强化学习智能体在未见过的实例上表现出更好的泛化性能。具体来说，与在整个实例集上训练的智能体相比，使用实例选择方法训练的智能体在测试集上的性能提升了未知百分比（论文中未给出具体数值，需要查阅原文）。这表明实例选择方法能够有效地减少训练偏差，提高强化学习智能体的泛化能力。

🎯 应用场景

该研究成果可应用于各种需要动态算法配置的场景，例如自动机器学习(AutoML)、超参数优化、机器人控制等。通过选择具有代表性的训练实例，可以提高强化学习智能体的泛化能力，使其能够更好地适应新的、未见过的任务。这有助于降低算法配置的成本，提高算法的性能，并最终推动人工智能技术的应用。

📄 摘要（原文）

Dynamic Algorithm Configuration (DAC) addresses the challenge of dynamically setting hyperparameters of an algorithm for a diverse set of instances rather than focusing solely on individual tasks. Agents trained with Deep Reinforcement Learning (RL) offer a pathway to solve such settings. However, the limited generalization performance of these agents has significantly hindered the application in DAC. Our hypothesis is that a potential bias in the training instances limits generalization capabilities. We take a step towards mitigating this by selecting a representative subset of training instances to overcome overrepresentation and then retraining the agent on this subset to improve its generalization performance. For constructing the meta-features for the subset selection, we particularly account for the dynamic nature of the RL agent by computing time series features on trajectories of actions and rewards generated by the agent's interaction with the environment. Through empirical evaluations on the Sigmoid and CMA-ES benchmarks from the standard benchmark library for DAC, called DACBench, we discuss the potentials of our selection technique compared to training on the entire instance set. Our results highlight the efficacy of instance selection in refining DAC policies for diverse instance spaces.