We study contextual bandits in the presence of a stage-wise constraint (a
constraint at each round), when the constraint must be satisfied both with high
probability and in expectation. Obviously the setting where the constraint is
in expectation is a relaxation of the one with high probability. We start with
the linear case where both the contextual bandit problem (reward function) and
the stage-wise constraint (cost function) are linear. In each of the high
probability and in expectation settings, we propose an upper-confidence bound
algorithm for the problem and prove a $T$-round regret bound for it. Our
algorithms balance exploration and constraint satisfaction using a novel idea
that scales the radii of the reward and cost confidence sets with different
scaling factors. We also prove a lower-bound for this constrained problem, show
how our algorithms and analyses can be extended to multiple constraints, and
provide simulations to validate our theoretical results. In the high
probability setting, we describe the minimum requirements for the action set in
order for our algorithm to be tractable. In the setting that the constraint is
in expectation, we further specialize our results to multi-armed bandits and
propose a computationally efficient algorithm for this setting with regret
analysis. Finally, we extend our results to the case where the reward and cost
functions are both non-linear. We propose an algorithm for this case and prove
a regret bound for it that characterize the function class complexity by the
eluder dimension.

我们在上下文感知强化学习中研究了阶段限制的情况，并提出了一种上界置信区间算法来平衡探索和约束满足，同时证明了其遗憾界。

带阶段约束的情境强化学习

Contextual Bandits with Stage-wise Constraints

We study the Low Rank Phase Retrieval (LRPR) problem defined as follows:
recover an $n \times q$ matrix $X^*$ of rank $r$ from a different and
independent set of $m$ phaseless (magnitude-only) linear projections of each of
its columns. To be precise, we need to recover $X^*$ from $y_k := |A_k{}'
x^*_k|, k=1,2,\dots, q$ when the measurement matrices $A_k$ are mutually
independent. Here $y_k$ is an $m$ length vector, $A_k$ is an $n \times m$
matrix, and $'$ denotes matrix transpose. The question is when can we solve
LRPR with $m \ll n$? A reliable solution can enable fast and low-cost phaseless
dynamic imaging, e.g., Fourier ptychographic imaging of live biological
specimens. In this work, we develop the first provably correct approach for
solving this LRPR problem. Our proposed algorithm, Alternating Minimization for
Low-Rank Phase Retrieval (AltMinLowRaP), is an AltMin based solution and hence
is also provably fast (converges geometrically). Our guarantee shows that
AltMinLowRaP solves LRPR to $\epsilon$ accuracy, with high probability, as long
as $m q \ge C n r^4 \log(1/\epsilon)$, the matrices $A_k$ contain i.i.d.
standard Gaussian entries, and the right singular vectors of $X^*$ satisfy the
incoherence assumption from matrix completion literature. Here $C$ is a
numerical constant that only depends on the condition number of $X^*$ and on
its incoherence parameter. Its time complexity is only $ C mq nr
\log^2(1/\epsilon)$. Since even the linear (with phase) version of the above
problem is not fully solved, the above result is also the first complete
solution and guarantee for the linear case. Finally, we also develop a simple
extension of our results for the dynamic LRPR setting.

本文研究了低秩相位恢复问题，提出了一种基于 AltMin 算法的解决方案，并给出了理论保证。此方法能有效地实现低成本、高速的相位动态成像，对生物样本的傅里叶 ptychographic 成像具有重要应用价值。

可证明的低秩相位恢复

Provable Low Rank Phase Retrieval

We propose a definition of causality for time series in terms of the effect
of an intervention in one component of a multivariate time series on another
component at some later point in time. Conditions for identifiability,
comparable to the back-door and front-door criteria, are presented and can also
be verified graphically. Computation of the causal effect is derived and
illustrated for the linear case.

本文提出了关于时间序列因果关系的定义，主要包括干预、识别性、线性求因果效应等；通过图形验证，给出了可比较的鉴别条件；最后以线性模型为例，详细论述了因果效应的计算方法。