tree-form sequential decision making (TFSDM) extends classical one-shot
decision making by modeling tree-form interactions between an agent and a
potentially adversarial environment. It captures the online decision-making
problems that each player faces in an extensive-form game, as we
本研究提出了一种基于在线随机梯度下降的广义线性赌博机算法，它使用单步 SGD 更新来利用过去的信息并使用汤普森抽样实现探索，能够在探索与利用之间取得平衡，在合成和实际数据集上始终优于现有算法，其总时间复杂度为 T 和 d 的线性比例，其中 T 是总轮次数，d 是特征数量，并实现了 O（T）的遗憾，其中 T 是回合数。
通过提供一种具有与最佳近似算法（在已知分布下）相对于平方根的 T 乘以 log T 束缚的通用在线学习算法，在半探测器环境中解决了在一大类 “单调” 随机问题中对于未知分布是否能够获得良好（近似）算法进行学习的问题。我们的框架适用于随机优化的若干基本问题，如先知不等式、潘多拉盒、随机背包、随机匹配和随机次模优化。