We develop and analyze algorithms for instrumental variable regression by
viewing the problem as a conditional stochastic optimization problem. In the
context of least-squares instrumental variable regression, our algorithms
neither require matrix inversions nor mini-batches and provides a fully online
approach for performing instrumental variable regression with streaming data.
When the true model is linear, we derive rates of convergence in expectation,
that are of order $\mathcal{O}(\log T/T)$ and $\mathcal{O}(1/T^{1-\iota})$ for
any $\iota>0$, respectively under the availability of two-sample and one-sample
oracles, respectively, where $T$ is the number of iterations. Importantly,
under the availability of the two-sample oracle, our procedure avoids
explicitly modeling and estimating the relationship between confounder and the
instrumental variables, demonstrating the benefit of the proposed approach over
recent works based on reformulating the problem as minimax optimization
problems. Numerical experiments are provided to corroborate the theoretical
results.

通过将问题视为条件随机优化问题，我们开发并分析了工具变量回归算法。在最小二乘工具变量回归的背景下，我们的算法既不需要矩阵求逆也不需要小批量处理，并为使用流数据进行工具变量回归提供了完全的在线方法。当真实模型是线性的时，对于任意的正数 iota，在具有两个样本和一个样本估计器的情况下，我们推导出期望意义下的收敛速度，分别为 O (log T/T) 和 O (1/T^(1-iota))，其中 T 是迭代次数。重要的是，在具有两个样本估计器的情况下，我们的方法避免了显式建模和估计混淆因子与工具变量之间的关系，展示了该方法相对于基于重定义问题为极小化极大化优化问题的最近工作的优势。数值实验验证了理论结果。

基于流数据的工具变量回归的随机优化算法

Stochastic Optimization Algorithms for Instrumental Variable Regression  with Streaming Data

JPS (Jump Point Search) is a state-of-the-art optimal algorithm for online
grid-based pathfinding. Widely used in games and other navigation scenarios,
JPS nevertheless can exhibit pathological behaviours which are not well
studied: (i) it may repeatedly scan the same area of the map to find
successors; (ii) it may generate and expand suboptimal search nodes. In this
work, we examine the source of these pathological behaviours, show how they can
occur in practice, and propose a purely online approach, called Constrained JPS
(CJPS), to tackle them efficiently. Experimental results show that CJPS has low
overheads and is often faster than JPS in dynamically changing grid
environments: by up to 7x in large game maps and up to 14x in pathological
scenarios.

本文提出了一种在线运用的优化算法 Constrained JPS，用于解决 JPS 算法在动态环境下出现的重复扫描地图和扩张次优搜索节点的异常行为，实验证明该方法在大型游戏地图和病态情形下比 JPS 算法更快且效率更高。

优化跳点搜索算法中的重复工作

Reducing Redundant Work in Jump Point Search

Algorithm selection is typically based on models of algorithm performance,
learned during a separate offline training sequence, which can be prohibitively
expensive. In recent work, we adopted an online approach, in which a
performance model is iteratively updated and used to guide selection on a
sequence of problem instances. The resulting exploration-exploitation trade-off
was represented as a bandit problem with expert advice, using an existing
solver for this game, but this required the setting of an arbitrary bound on
algorithm runtimes, thus invalidating the optimal regret of the solver. In this
paper, we propose a simpler framework for representing algorithm selection as a
bandit problem, with partial information, and an unknown bound on losses. We
adapt an existing solver to this game, proving a bound on its expected regret,
which holds also for the resulting algorithm selection technique. We present
preliminary experiments with a set of SAT solvers on a mixed SAT-UNSAT
benchmark.

本文提出一种将算法选择表示为部分信息的赌博问题的简单框架，并将现有的求解器适应于该游戏，证明了其期望遗憾的边界，该算法选择技术的也适用于此。