A few typos and small errors I spotted in Chapter 2

[richardcsuwandi]

Hi Alex,

Really enjoying the book so far! I read through the first two chapters closely and found a handful of small things worth flagging (some are just typos, a couple are places where the math notation doesn't quite say what I think you meant). Details below.

1. A few parentheses missing in the regret formulas

In Definition 2.16 (eq. 2.5), the formula for regret is written as:

R_T(p, r) = E_{a_t~p} sup_{a in A} sum_{t=1}^T r(a) - r(a_t)

As written, the sum only applies to r(a), so the minus sign ends up attached to just the last r(a_t) term instead of being inside the sum. It should probably be:

R_T(p, r) = E_{a_t~p} sum_{t=1}^T \left( sup_{a in A} r(a) - r(a_t) \right)

with the difference wrapped in parentheses inside the sum. I think this is just a typesetting slip, since the proofs later on (e.g. Proposition 2.25) do use the correct grouping.

The same thing happens in a few other spots that use this same formula shape:

• Definition 2.20, eq. (2.12)
• Definition 2.24, eq. (2.15)
• the "best action in hindsight" formula, eq. (2.16)
• Proposition 2.25, eq. (2.18)
• Proposition 2.26, eq. (2.23)
• the inline formula in Lemma 2.34
• Proposition 2.35, eq. (2.81)

Simple regret, eq. (2.6), has the same issue too, though it's less confusing there since there's no sum to worry about, but still, adding parentheses (sup_{a} r(a) - r(a_T)) would make it clearer I think.

2. Small typos

• Right after Example 2.10, and twice in Theorem 2.23 (once in the statement, once in the restatement in §2.7): "As consequence" should be "As a consequence."
• In §2.5 ("Our perspective will be to take both approaches seriously..."): "different strength and weaknesses" should be "different strengths and weaknesses."
• In §2.5.1, the Bayesian optimization paragraph: "Garnett (2023) provide a comprehensive treatment" should be "provides" (Garnett is one author).
• In the chapter's opening paragraph: "understand what is a decision-making problem, what is an algorithm... assess performance of a given algorithm" reads a bit awkwardly — maybe "understand what a decision-making problem is, what an algorithm is... assess the performance of a given algorithm"?
• Right after Lemma 2.34's proof, in §2.4: "There is nothing an algorithm can learn, it may as well play at random" — this reads as a run-on sentence. Maybe a semicolon instead of the comma ("...can learn; it may as well play at random"), or add a "so."

3. Some possible notation inconsistencies

• Example 2.3: The feedback is written as sigma(r,a) = r(a) + epsilon(a), but epsilon is defined as a single Gaussian N(0,1), i.e. a scalar, not a function of the arm a. Example 2.5 handles this correctly by indexing the noise (epsilon_n), so maybe Example 2.3 should do the same.
• Example 2.10: The observation space is defined as Sigma = {(s, a, r) : N -> S x A x R}, which isn't quite valid set-builder notation. I think you mean something like Sigma = (S x A x R)^N (the space of infinite sequences). Also, r gets used for three different things in this example (the MDP reward, the episodic reward, and a coordinate of the trajectory), so might be worth a different symbol for one of them.
• Definition 2.21 (Underlying MDP): The state is defined as just the history Seq(A x Sigma), but since Bayesian regret is finite-horizon, doesn't the state also need to track how much time is left? As written it seems like the optimal policy couldn't depend on t.
• Theorem 2.23: After the three equivalent conditions, it says "one can define the Blackwell order <= over feedback functions", but the order itself is never actually spelled out. Maybe just a one-liner like "sigma_2 <= sigma_1 iff there's a garbling g with sigma_2(r,a) = g(sigma_1(r,a), a)"?
• Proposition 2.26, eq. (2.23): a*_r shows up without being defined, I'm guessing it's meant to be the maximizer of r.
• Lemma 2.34: The very last step, "thus we have C <= R_T(p, r_p)," seems to be quietly relying on Lemma 2.33, but that's never mentioned, and r_p isn't actually part of the lemma's statement.
• In the proof of Theorem 2.23 (§2.7, Part I): the letter gamma gets reused here for a garbling / element of the set G (e.g. "varsigma ~ gamma(. | r)", "gamma = delta_{varsigma*_s}"), which clashes with gamma already meaning the discount factor from Definition 2.18 earlier in the chapter. Might be worth renaming one of them (e.g. g' or h) so they don't collide.

4. On the repo

In this repo's readme.md, the link on line 3 points to https://bayesianalgorithmc.com, which isn't the correct URL. I think you meant https://bayesianalgorithms.com.

---

Hope this helps! Looking forward to reading the other chapters as they come out.

Best,
Richard