I think this must have been done before, possibly with martingales, but I can't find anything online!
Given $X_1,\dots,X_n$ independent, each $X_i \in [a_i,b_i]$, letting $S_i = \sum_{j=1}^i X_j$, do you know of a good bound of the form $$ \Pr\Big[\exists i ~\text{ s.t. }~ \big|S_i - E[S_i]\big| > k\Big] \leq f(k) ? $$
The naive approach would be to separately use a Chernoff bound on each $S_i$, then union bound over all $n$ events. At its worst/roughest, this gives $$ \Pr\Big[\exists i ~\text{ s.t. }~ \big|S_i - E[S_i]\big| > k\Big] \leq n e^{-k^2 / \sum_{i=1}^n (b_i-a_i)^2}. $$ You might improve this a little with tweaking, but my intuition is that intuitively, this approach is too conservative because, for instance, given that $|S_n - E[S_n]| \leq k$, it seems very likely that all intermediate $S_i$ are within $k$ of their mean as well.
(Notice that we are not being very demanding: we don't require them to all be multiplicatively close to their means, and we don't require the averages $\frac{S_i}{i}$ to all be within some value of their expectation; those situations seem harder than what we want here!)
No approach seems obvious to me (one I thought of trying is to take it term-by-term...?). Any help or references would be great! Thanks!
It looks like Etemadi's Inequality has what I'm looking for:
$\Pr[\exists i s.t. |S_i - E[S_i]| > 3k] \leq 3 \max_i \Pr[|S_i - E[S_i]| > k] .$
The maximum probability occurs for $i=n$. So here, just use Hoeffding:
$= 6 e^{-k^2 / 2 \sum_i (b_i - a_i)^2}$.