近日，上海交通大学电子信息与电气工程学院约翰·霍普克罗夫特计算机科学中心长聘教轨副教授李帅团队在针对线性老虎机问题的研究中取得了重要进展，研究成果“Best-of-three-worlds Analysis for Linear Bandits with Follow-the-regularized-leader Algorithm”（线性老虎机问题上基于FTRL算法的三环境最优性分析）被机器学习理论方向的顶级国际会议国际学习理论大会（Annual Conference on Learning Theory，COLT 2023）录用。本篇论文的所有作者均来自上海交通大学，第一和第二作者分别是李帅指导的三年级直博生孔芳和二年级直博生赵灿哲，李帅为通讯作者。这是上海交通大学首次在COLT上发表论文，且为唯一完成单位。

论文首次证明了follow-the-regularized-leader（FTRL）类型的算法可以使得线性老虎机问题在随机和对抗环境下都能取得（近似）最优累积懊悔的理论保证。相关研究工作受到国家自然科学基金等项目的支持。

研究背景

多臂老虎机算法研究在交互过程中如何设计出有效学习并快速收敛的算法，是强化学习领域的一个重要分支，在推荐、广告、搜索、在线测试等领域有着丰富的应用。在实际场景中，由于问题涉及的选择空间非常大，通常会考虑引入特征表示与线性结构来提升学习效率与算法的适用性，即线性老虎机问题。与多臂老虎机问题类似，线性老虎机问题的学习目标为最大化算法的累积收益，等价于最小化累积懊悔，即算法的累积收益与算法的最优选择之间的差。随机环境与对抗环境是多臂老虎机问题中常见的两种研究场景，分别考虑算法面对较为稳定的交互式场景和变化剧烈的交互式场景中的学习表现。

线性老虎机问题的重要性

已有算法可以在随机场景或者对抗场景中得到累积懊悔的最优理论保证，但是通常需要关于交互场景的先验性质，而当实际运行的环境与算法设计的环境不同，算法可能得不到良好的学习表现。近期一些研究工作考虑了多臂老虎机问题，分别提出了基于环境检测的方法与基于follow-the-regularized-leader （FTRL）框架的方法，使得算法可以同时处理随机场景与对抗场景，提升了算法的鲁棒性。其中，基于环境检测的方法一旦检测到环境变化便对运行算法进行切换，设计与分析较为容易，但算法的适应性不够，如果环境多次变化会造成算法的整体运行不够流畅自然。而基于FTRL框架的算法有更好的环境适应性，且理论结果更优。针对线性老虎机问题，已有工作仅讨论了基于环境检测的方法，是否存在具有良好环境适应性的、基于FTRL框架的算法是领域中的重要开放性问题。

研究成果

论文首次提出了基于FTRL框架的线性老虎机算法，基于香农熵势函数自适应地处理随机环境、对抗环境以及有少量反馈污染的交互环境，不再需要主动检测环境变化，可以同时在多种不同场景中得到（近似）最优累积懊悔的理论保证。

本文主要结果

该工作呈现了较高的算法自适应性，进一步挖掘了FTRL算法框架在交互式场景中的潜力，改进了线性老虎机问题的已有理论成果，解决了领域中一个重要的开放性问题，为多臂老虎机算法进行大规模的应用部署提供了更优秀的算法支撑。

算法核心设计思路

论文链接：https://arxiv.org/abs/2303.06825

个人介绍

李帅，上海交通大学长聘教轨副教授，研究方向为强化学习算法与机器学习理论。李帅曾获得浙江大学竺可桢学院数学学士学位、中国科学院数学与系统科学研究院基础数学硕士学位、香港中文大学计算机科学与工程博士学位，于2019年加入上海交通大学约翰·霍普克罗夫特计算机科学中心。李帅曾于2018年获得谷歌全球博士奖学金，2020年获得上海市扬帆人才计划。

关于COLT

COLT始于1988年，由计算学习协会（Association for Computational Learning，ACL）主办，是机器学习理论方向的顶级国际会议，也是该领域公认的录取难度最高的会议。截至2022年，中国大陆科研机构和高校作为唯一单位独立完成的论文仅有4篇。被录用的稿件反映了机器学习理论最前沿的研究水平。