$\displaystyle+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})+2\max_{p_{0}\in\mathcal{P}_{0}}\alpha(\mathcal{E}_{3,p_{0}})}{\varepsilon}\,.$

###### Proof of Theorem 2.

By Theorem 1, we have

$\displaystyle\mathbb{E}_{\pi_{1:T}}\left[\alpha(E)\right]\leq
O\left(\frac{|\mathcal{Y}|\ln(|\mathcal{Y}||\mathcal{E}|T)}{T}+\frac{|\mathcal{Y}|\sqrt{\ln(|\mathcal{Y}||\mathcal{E}|T)|\\{t:E(\pi_{t})=1|\\}}}{T}\right)\,.$

Hence, we have:

$\displaystyle\mathbb{E}_{\pi_{1:T}}\left[\alpha(\mathcal{E}_{1})\right]\leq\mathcal{O}(\frac{|\mathcal{Y}|\ln(|\mathcal{Y}|(|\mathcal{P}_{\mathcal{O}}|+|\mathcal{P}_{0}|)\left|\mathcal{A}\right|T)}{T}+\left|\mathcal{Y}\right|\sqrt{\frac{\ln(|\mathcal{Y}|(|\mathcal{P}_{\mathcal{O}}|+|\mathcal{P}_{0}|)\left|\mathcal{A}\right|T)\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|}{T}})\,,$
$\displaystyle\mathbb{E}_{\pi_{1:T}}\left[\alpha(\mathcal{E}_{2})\right]\leq\mathcal{O}(\frac{|\mathcal{Y}|\ln(|\mathcal{Y}|(|\mathcal{P}_{\mathcal{O}}|+|\mathcal{P}_{0}|)\left|\mathcal{A}\right|T)}{T}+\left|\mathcal{Y}\right|\sqrt{\frac{\ln(|\mathcal{Y}|(|\mathcal{P}_{\mathcal{O}}|+|\mathcal{P}_{0}|)\left|\mathcal{A}\right|T)\left|\mathcal{P}_{0}\right|\left|\mathcal{A}\right|}{T}})\,,$
$\displaystyle\mathbb{E}_{\pi_{1:T}}\left[\alpha(\mathcal{E}_{3,p_{0}})\right]\leq\mathcal{O}(\frac{|\mathcal{Y}|\ln(|\mathcal{Y}|(|\mathcal{P}_{\mathcal{O}}|+|\mathcal{P}_{0}|)\left|\mathcal{A}\right|T)}{T}+\left|\mathcal{Y}\right|\sqrt{\frac{\ln(|\mathcal{Y}|(|\mathcal{P}_{\mathcal{O}}|+|\mathcal{P}_{0}|)\left|\mathcal{A}\right|T)\left|\mathcal{A}\right|}{T}})\,.$

By taking expectation over $\pi_{1:T}$ and plugging these values into Theorem
6, we have

$\displaystyle\text{PR}(\sigma^{\dagger},\mathcal{L},y_{1:T})\leq\widetilde{\mathcal{O}}\left(c+\gamma+\sqrt{\left|\mathcal{P}_{0}\right|\left|\mathcal{A}\right|/T}+\frac{\varepsilon_{\textrm{swap}}+\left|\mathcal{Y}\right|\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|/T}}{\beta}+\frac{\varepsilon_{\textrm{swap}}+\left|\mathcal{Y}\right|\sqrt{\left|\mathcal{A}\right|/T}}{\varepsilon}\right)\,.$

Hence we are done with proof of Theorem 2. ∎

###  B.1 Proof of Theorem 6

See 6

###### Proof.

For any sequence of states $y_{1:T}$ and sequence of forecasts $\pi_{1:T}$,
and any constant policy $p_{0}\in\mathcal{P}_{0}$, for any realized sequence
of actions $a_{1:T}$ and $a^{p_{0}}_{1:T}$, we can decompose the (realized)
regret compared with constant mechanism $\sigma^{p_{0}}$ as

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}\left(V(a_{t}^{p_{0}},{p_{0}},y_{t})-V(a_{t},p_{t},y_{t})\right)$
$\displaystyle=$
$\displaystyle\frac{1}{T}\left(\underbrace{\sum_{t=1}^{T}(V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},y_{t})-V(r_{t},p_{t},y_{t}))}_{(a)}+\underbrace{\sum_{t=1}^{T}(V(r_{t},p_{t},y_{t})-V(a_{t},p_{t},y_{t}))}_{(b)}\right.$
$\displaystyle\left.+\underbrace{\sum_{t=1}^{T}(V(a_{t}^{p_{0}},{p_{0}},y_{t})-V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},y_{t}))}_{(c)}\right)$

  1. 1.

We bound term (a) using the fact that $p_{t}$ is a
$(c,\varepsilon,\beta,\gamma)$-optimal stable policy under $\pi_{t}$.
According to the definition of stable policy oracle (Definition 4), we have
$V(r_{t},p_{t},\pi_{t})\geq
V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},\pi_{t})-c$. Then
since $\pi_{1:T}$ has $\alpha$ bias conditional on $(p_{t},r_{t})$ and
$(p_{t}^{\textrm{optimistic}},a_{t}^{\textrm{optimistic}})$, we have

$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(r_{t},p_{t},y_{t})\geq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(r_{t},p_{t},\pi_{t})-\alpha(\mathcal{E}_{1})$
($\mathcal{E}_{1}$-bias) $\displaystyle\geq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},\pi_{t})-c-\alpha(\mathcal{E}_{1})$
(stabilization) $\displaystyle\geq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},y_{t})-c-\alpha(\mathcal{E}_{2})-\alpha(\mathcal{E}_{1})\,.$
($\mathcal{E}_{2}$-bias)

Therefore, we have

$\text{Term (a)}\leq(c+\alpha(\mathcal{E}_{2})+\alpha(\mathcal{E}_{1}))T\,.$

  2. 2.

We bound term (c) using the fact that
$V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},\pi_{t})$ is the
optimal optimistic achievable utility of the Principal.

For constant mechanism $\sigma^{p_{0}}$, let $t\in(r)$ denote
$t:r^{p_{0}}_{t}=r$. Let $n^{p_{0}}_{r}=\sum_{t\in(r)}1$ denote the number of
rounds in which $r$ is recommended. Let

$\displaystyle
b^{p_{0}}_{r}=\frac{1}{n^{p_{0}}_{r}}\max\left(\left|\sum_{t:r_{t}=r}U(a_{t}^{p_{0}},p,y_{t})-U(\widehat{\mu}^{p_{0}}_{r},p,y_{t})\right|,\left|\sum_{t:r_{t}=r}V(a_{t}^{p_{0}},p,y_{t})-V(\widehat{\mu}^{p_{0}}_{r},p,y_{t})\right|\right)\,.$

By Assumption 2, we have
$\mathbb{E}_{\mathcal{L}}\left[b^{p_{0}}_{r}\right]=\mathcal{O}(\frac{1}{\sqrt{n^{p_{0}}_{r}}})$.
Let
$\widehat{\mu}^{p_{0}}_{r}=\frac{1}{n^{p_{0}}_{r}}\sum_{t\in(r)}a^{p_{0}}_{t}$
denote the empirical distribution of Agent’s action in the subsequence where
$r$ is the recommendation. Let

$\textrm{SwapReg}^{p_{0}}_{r}=\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t\in(r)}\left(U(h(a^{p_{0}}_{t}),p_{0},y_{t})-U(a^{p_{0}}_{t},{p_{0}},y_{t})\right)$

denote the swap regret in this subsequence and let
$\textrm{SwapReg}^{p_{0}}=\sum_{r\in\mathcal{A}}\textrm{SwapReg}^{p_{0}}_{r}$
denote the swap regret for $a^{p_{0}}_{1:T}$. Then we have

$\displaystyle\sum_{t\in(r)}U(\widehat{\mu}^{p_{0}}_{r},p_{0},\pi_{t})$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(r)}U(\widehat{\mu}^{p_{0}}_{r},p_{0},y_{t})-\alpha(E_{3,p_{0},r})T$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(r)}U(a_{t}^{p_{0}},p_{0},y_{t})-n^{p_{0}}_{r}b^{p_{0}}_{r}-\alpha(E_{3,p_{0},r})T$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(r)}U(r,p_{0},y_{t})-\textrm{SwapReg}^{p_{0}}_{r}-n^{p_{0}}_{r}b^{p_{0}}_{r}-\alpha(E_{3,p_{0},r})T$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(r)}U(r,{p_{0}},\pi_{t})-\textrm{SwapReg}^{p_{0}}_{r}-n^{p_{0}}_{r}b^{p_{0}}_{r}-2\alpha(E_{3,p_{0},r})T\,,$
(9)

where the last inequality again uses our bound on $\mathcal{E}_{3}$-bias. For
a random action $a\sim\widehat{\mu}^{p_{0}}_{r}$, let $F_{t}$ denote the event
that $U(a,{p_{0}},\pi_{t})<U(r,{p_{0}},\pi_{t})-\varepsilon$. We have

$\displaystyle\sum_{t\in(r)}U(\widehat{\mu}^{p_{0}}_{r},p_{0},\pi_{t})$
$\displaystyle=$
$\displaystyle\sum_{t\in(r)}\left(\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(F_{t})\mathbb{E}\left[U(a,{p_{0}},\pi_{t})\left|F_{t}\right.\right]+\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(\neg
F_{t})\mathbb{E}\left[U(a,{p_{0}},\pi_{t})\left|\neg
F_{t}\right.\right]\right)$ $\displaystyle\leq$
$\displaystyle\sum_{t\in(r)}\left(\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(F_{t})(U(r,{p_{0}},\pi_{t})-\varepsilon)+\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(\neg
F_{t})U(r,{p_{0}},\pi_{t})\right)\,.$

By combining with Eq (9), we have

$\displaystyle\sum_{t\in(r)}\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(F_{t})\leq\frac{\textrm{SwapReg}^{p_{0}}_{r}+n^{p_{0}}_{r}b^{p_{0}}_{r}+2\alpha(E_{3,p_{0},r})T}{\varepsilon}\,.$
(10)

We also have:

$\displaystyle V(\widehat{\mu}^{p_{0}}_{r},p_{0},\pi_{t})\leq$
$\displaystyle\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(\neg
F_{t})\max_{\widetilde{r}\in\mathcal{B}(p_{0},\pi_{t},\varepsilon)}V(\widetilde{r},p_{0},\pi_{t})+\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(F_{t})$
$\displaystyle\leq$
$\displaystyle\max_{\widetilde{r}\in\mathcal{B}(p_{0},\pi_{t},\varepsilon)}V(\widetilde{r},p_{0},\pi_{t})+\Pr_{a\sim\widehat{\mu}^{p_{0}}_{r}}(F_{t})\,.$
(11)

By combining Eqs (10) and (11), we have

$\displaystyle\sum_{t\in(r)}\max_{\widetilde{r}\in\mathcal{B}(p_{0},\pi_{t},\varepsilon)}V(\widetilde{r},p_{0},\pi_{t})\geq\sum_{t\in(r)}V(\widehat{\mu}^{p_{0}}_{r},p_{0},\pi_{t})-\frac{\textrm{SwapReg}^{p_{0}}_{r}+n^{p_{0}}_{r}b^{p_{0}}_{r}+2\alpha(E_{3,p_{0},r})T}{\varepsilon}\,.$
(12)

Then we have

$\displaystyle\sum_{t=1}^{T}V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},y_{t})$
$\displaystyle\geq$
$\displaystyle\sum_{t=1}^{T}V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},\pi_{t})-\alpha(\mathcal{E}_{2})T$
($\mathcal{E}_{2}$-bias) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}\max_{\widetilde{p}\in\mathcal{P}}\max_{\widetilde{r}\in\mathcal{B}(\widetilde{p},\pi_{t},\varepsilon)}V(\widetilde{r},\widetilde{p},\pi_{t})-\alpha(\mathcal{E}_{2})T$
(definition of $(p_{t}^{\textrm{optimistic}},a_{t}^{\textrm{optimistic}})$)
$\displaystyle\geq$
$\displaystyle\sum_{t=1}^{T}\max_{\widetilde{r}\in\mathcal{B}(p_{0},\pi_{t},\varepsilon)}V(\widetilde{r},p_{0},\pi_{t})-\alpha(\mathcal{E}_{2})T$
$\displaystyle=$
$\displaystyle\sum_{r\in\mathcal{A}}\sum_{t\in(r)}\max_{\widetilde{r}\in\mathcal{B}(p_{0},\pi_{t},\varepsilon)}V(\widetilde{r},p_{0},\pi_{t})-\alpha(\mathcal{E}_{2})T$
$\displaystyle\geq$
$\displaystyle\sum_{r\in\mathcal{A}}\left(\sum_{t\in(r)}V(\widehat{\mu}^{p_{0}}_{r},p_{0},\pi_{t})-\frac{\textrm{SwapReg}^{p_{0}}_{r}+n^{p_{0}}_{r}b^{p_{0}}_{r}+2\alpha(E_{3,p_{0},r})T}{\varepsilon}\right)-\alpha(\mathcal{E}_{2})T$
(applying Eq (12)) $\displaystyle\geq$
$\displaystyle\sum_{r\in\mathcal{A}}\sum_{t\in(r)}V(\widehat{\mu}^{p_{0}}_{r},p_{0},y_{t})-\frac{\textrm{SwapReg}^{p_{0}}+\sum_{r\in\mathcal{A}}n^{p_{0}}_{r}b^{p_{0}}_{r}+2\alpha(\mathcal{E}_{3,p_{0}})T}{\varepsilon}-\alpha(\mathcal{E}_{3,p_{0}})T-\alpha(\mathcal{E}_{2})T$
($\mathcal{E}_{3}$-bias) $\displaystyle\geq$
$\displaystyle\sum_{t}V(a_{t}^{p_{0}},p_{0},y_{t})-\sum_{r\in\mathcal{A}}n^{p_{0}}_{r}b^{p_{0}}_{r}-\frac{\textrm{SwapReg}^{p_{0}}+\sum_{r\in\mathcal{A}}n^{p_{0}}_{r}b^{p_{0}}_{r}+2\alpha(\mathcal{E}_{3,p_{0}})T}{\varepsilon}-(\alpha(\mathcal{E}_{3,p_{0}})+\alpha(\mathcal{E}_{2}))T\,.$
(no secret info)

Hence, we have

$\displaystyle\text{Term (c)}=$
$\displaystyle\sum_{t=1}^{T}V(a_{t}^{p_{0}},{p_{0}},y_{t})-V(a_{t}^{\textrm{optimistic}},p_{t}^{\textrm{optimistic}},y_{t})$
$\displaystyle\leq$
$\displaystyle\sum_{r\in\mathcal{A}}n^{p_{0}}_{r}b^{p_{0}}_{r}+\frac{\textrm{SwapReg}^{p_{0}}+\sum_{r\in\mathcal{A}}n^{p_{0}}_{r}b^{p_{0}}_{r}+2\alpha(\mathcal{E}_{3,p_{0}})T}{\varepsilon}+(\alpha(\mathcal{E}_{3,p_{0}})+\alpha(\mathcal{E}_{2}))T\,.$

By taking expectation over the randomness of the Agent’s learning algorithm
$\mathcal{L}$, we have

$\mathbb{E}_{\mathcal{L}}\left[\text{Term
(c)}\right]\leq\left(\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})+2\alpha(\mathcal{E}_{3,p_{0}})}{\varepsilon}+\alpha(\mathcal{E}_{3,p_{0}})+\alpha(\mathcal{E}_{2})\right)T\,.$

  3. 3.

We bound term (b) by proving that the number of rounds in which the Agent does
not follow the recommendation $r_{t}$ is small using the fact that that
$p_{t}$ is $(\beta,\gamma)$-stable under $\pi_{t}$.

For proposed mechanism, let $t\in(p,r)$ denote $t:(p_{t},r_{t})=(p,r)$. Let
$n_{p,r}=\sum_{t=1}^{T}\mathds{1}[t\in(p,r)]$ denote the number of rounds in
which $(p_{t},r_{t})=(p,r)$.

$\displaystyle
b_{p,r}=\frac{1}{n_{p,r}}\max\left(\left|\sum_{t\in(p,r)}U(a_{t},p,y_{t})-U(\widehat{\mu}_{p,r},p,y_{t})\right|,\left|\sum_{t\in(p,r)}V(a_{t},p,y_{t})-V(\widehat{\mu}_{p,r},p,y_{t})\right|\right)\,.$

By Assumption 2, we have
$\mathbb{E}_{\mathcal{L}}\left[b_{p,r}\right]=\mathcal{O}(\frac{1}{\sqrt{n_{p,r}}})$.
Let $\widehat{\mu}_{p,r}=\frac{1}{n_{p,r}}\sum_{t\in(p,r)}a_{t}$ denote the
empirical distribution of the actions on this subsequence. Let
$\widehat{y}_{p,r}=\frac{1}{n_{p,r}}\sum_{t\in(p,r)}y_{t}$ denote the
empirical distribution of states in these rounds and
$\pi_{p,r}=\frac{1}{n_{p,r}}\sum_{t\in(p,r)}\pi_{t}$ denote the empirical
distribution of the forecasts. Let

$\textrm{SwapReg}_{p,r}=\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t\in(p,r)}\left(U(h(a_{t}),p_{t},y_{t})-U(a_{t},p_{t},y_{t})\right)$

denote the swap regret for the Agent over the subsequence in which
$(p_{t},r_{t})=(p,r)$ and let
$\textrm{SwapReg}=\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}\textrm{SwapReg}_{p,r}$
denote the total swap regret (for the action sequence $a_{1:T}$).

In the rounds in which $(p_{t},r_{t})=(p,r)$, similar to Eq (9), we have

$\displaystyle\sum_{t\in(p,r)}U(\widehat{\mu}_{p,r},p,\pi_{t})$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(p,r)}U(\widehat{\mu}_{p,r},p,y_{t})-\alpha(E_{1,p,r})T$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(p,r)}U(a_{t},p,y_{t})-n_{p,r}b_{p,r}-\alpha(E_{1,p,r})T$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(p,r)}U(r,p,y_{t})-\textrm{SwapReg}_{p,r}-n_{p,r}b_{p,r}-\alpha(E_{1,p,r})T$
$\displaystyle\geq$
$\displaystyle\sum_{t\in(p,r)}U(r,p,\pi_{t})-\textrm{SwapReg}_{p,r}-n_{p,r}b_{p,r}-2\alpha(E_{1,p,r})T\,.$
($\mathcal{E}_{1}$-bias)

Since $p$ is $(\beta,\gamma)$-stable under $\pi_{t}$ for all $t\in(p,r)$, we
have $U(a,p,\pi_{t})\leq U(r,p,\pi_{t})-\beta$ or $V(a,p,\pi_{t})\geq
V(r,p,\pi_{t})-\gamma$ for all $a\neq r$ in $\mathcal{A}$. Let
$\rho_{p,r,t}=\Pr_{a\sim\widehat{\mu}_{p,r}}(U(a,p,\pi_{t})\leq
U(r,p,\pi_{t})-\beta)$ denote the probability of $U(a,p,\pi_{t})\leq
U(r,p,\pi_{t})-\beta$ for $a\sim\widehat{\mu}_{p,r}$. By combining with
$U(a,p,\pi_{t})\leq U(r,p,\pi_{t})$ for all $a\in\mathcal{A}$, we have

$\sum_{t\in(p,r)}\rho_{p,r,t}\leq\frac{\textrm{SwapReg}_{p,r}+n_{p,r}b_{p,r}+2\alpha(E_{1,p,r})T}{\beta}\,.$
(13)

Therefore, we have

$\displaystyle\text{Term (b)}=$
$\displaystyle\sum_{t=1}^{T}(V(r_{t},p_{t},y_{t})-V(a_{t},p_{t},y_{t}))$
$\displaystyle\leq$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}\sum_{t\in(p,r)}(V(r,p,y_{t})-V(\widehat{\mu}_{p,r},p,y_{t}))+\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}n_{p,r}b_{p,r}$
(no secret info) $\displaystyle\leq$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}\sum_{t\in(p,r)}V(r,p,\pi_{t})-V(\widehat{\mu}_{p,r},p,\pi_{t})+2\alpha(\mathcal{E}_{1})T+\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}n_{p,r}b_{p,r}$
($\mathcal{E}_{1}$-bias) $\displaystyle\leq$ $\displaystyle\gamma
T+\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}\sum_{t\in(p,r)}\rho_{p,r,t}+2\alpha(\mathcal{E}_{1})T+\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}n_{p,r}b_{p,r}$
(stability of $p$) $\displaystyle\leq$ $\displaystyle\gamma
T+\frac{\textrm{SwapReg}+\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}n_{p,r}b_{p,r}+2\alpha(\mathcal{E}_{1})T}{\beta}+2\alpha(\mathcal{E}_{1})T+\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}n_{p,r}b_{p,r}\,.$
(Apply Eq (13))

Hence, by taking the expectation over the randomness of the Agent’s algorithm
$\mathcal{L}$, we have

$\displaystyle\mathbb{E}_{\mathcal{L}}\left[\text{Term
(b)}\right]\leq\left(\gamma+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|/T})+2\alpha(\mathcal{E}_{1})}{\beta}+2\alpha(\mathcal{E}_{1})+\mathcal{O}(\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|/T})\right)T\,.$

Now we have the Principal’s regret upper bounded by

$\displaystyle\textrm{PR}(\mathcal{O}_{c,\varepsilon,\beta,\gamma},\pi_{1:T},\mathcal{L},y_{1:T})$
$\displaystyle\leq$ $\displaystyle
c+\alpha(\mathcal{E}_{2})+\alpha(\mathcal{E}_{1})$
$\displaystyle\gamma+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|/T})+2\alpha(\mathcal{E}_{1})}{\beta}+2\alpha(\mathcal{E}_{1})+\mathcal{O}(\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|/T})$
$\displaystyle\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})+2\max_{p_{0}\in\mathcal{P}_{0}}\alpha(\mathcal{E}_{3,p_{0}})}{\varepsilon}+\max_{p_{0}\in\mathcal{P}_{0}}\alpha(\mathcal{E}_{3,p_{0}})+\alpha(\mathcal{E}_{2})$
$\displaystyle=$ $\displaystyle
c+3\alpha(\mathcal{E}_{1})+2\alpha(\mathcal{E}_{2})+\max_{p_{0}\in\mathcal{P}_{0}}\alpha(\mathcal{E}_{3,p_{0}})+\gamma+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|\left|\mathcal{A}\right|/T})+2\alpha(\mathcal{E}_{1})}{\beta}$
$\displaystyle+\frac{\varepsilon_{\textrm{swap}}+\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})+2\max_{p_{0}\in\mathcal{P}_{0}}\alpha(\mathcal{E}_{3,p_{0}})}{\varepsilon}\,.$

Since $\left|\mathcal{P}_{0}\right|$ and $\left|\mathcal{A}\right|$ are
$\Theta(1)$, we have

$\displaystyle\textrm{PR}(\mathcal{O}_{c,\varepsilon,\beta,\gamma},\pi_{1:T},\mathcal{L},y_{1:T})$
$\displaystyle=$
$\displaystyle\mathcal{O}(c+\left|\mathcal{P}_{\mathcal{O}}\right|\alpha+\gamma+\frac{\varepsilon_{\textrm{swap}}+\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|/T}+\left|\mathcal{P}_{\mathcal{O}}\right|\alpha}{\beta}+\frac{\varepsilon_{\textrm{swap}}+\sqrt{1/T}+\alpha}{\varepsilon}+\sqrt{\left|\mathcal{P}_{\mathcal{O}}\right|/T})\,.$

∎

##  Appendix C Proofs from Section 5.1

######  Lemma 12.

For any $\pi$, and for any Agent actions $a_{1}$ and $a_{2}$ s.t. $a_{1}\neq
a_{2}$, there is a unique linear contract $p$ such that

$U(a_{1},p,\pi)=U(a_{2},p,\pi)$

###### Proof.

In order for two Agent actions to give the same payoff, we need a $p$ such
that

$\displaystyle pf(\pi,a_{1})-c(a_{1})=pf(\pi,a_{2})-c(a_{2})$ $\displaystyle
p=\frac{c(a_{1})-c(a_{2})}{f(\pi,a_{1})-f(\pi,a_{2})}$

If $f(\pi,a_{1})-f(\pi,a_{2})\neq 0$ this expression is well defined and has a
unique solution, and therefore there can be at most one $p$ for which this is
true. If $f(\pi,a_{1})=f(\pi,a_{2})$, then

$\displaystyle pf(\pi,a_{1})-c(a_{1})=pf(\pi,a_{1})-c(a_{2})$
$\displaystyle\Leftrightarrow c_{a_{1}}=c_{a_{2}}$

This is a contradiction, as we assume all costs are separated by
$\Delta_{c}\geq 0$. Therefore this expression must be well defined and have a
unique solution. ∎

See 3

###### Proof.

To show this, we will first show that for any Agent action $a^{*}$, there are
at most $2$ policies for which $a^{*}$ a non-unique best response. To see
this, let’s consider the smallest linear contract $p_{1}$ such that $a$ is a
best response. Let us also consider the largest linear contract $p_{2}$ such
that $a$ is a best response. We will show that for all $p$ such that
$p_{1}<p<p_{2}$, $a$ is a unique best response.

As $a^{*}$ is a best response to $p_{1}$, we have

$\displaystyle U(a^{*},p_{1},\pi)=\max_{a\in\mathcal{A}}U(a,p_{1},\pi)$
$\displaystyle\Leftrightarrow
p_{1}f(\pi,a^{*})-c(a^{*})=\max_{a\in\mathcal{A}}(p_{1}f(\pi,a)-c(a))$

Similarly,

$\displaystyle
p_{2}f(\pi,a^{*})-c(a^{*})=\max_{a\in\mathcal{A}}(p_{2}f(\pi,a)-c(a))$

Combining these, we get that, for any $x\in[0,1]$:

$\displaystyle(xp_{1}+(1-x)p_{2})\cdot
f(\pi,a^{*})-c(a^{*})=x\cdot\max_{a\in\mathcal{A}}(p_{1}f(\pi,a)-c(a))+(1-x)\cdot\max_{a\in\mathcal{A}}(p_{2}f(\pi,a)-c(a))$

Now, consider any action $\overline{a}\neq a^{*}$, evaluated on the linear
contract defined by $(xp_{1}+(1-x)p_{2})$. Assume for contradiction that
$\overline{a}$ is optimal on this contract. Then we have that

$\displaystyle(xp_{1}+(1-x)p_{2})\cdot
f(\pi,\overline{a})-c(\overline{a})=x(p_{1}f(\pi,\overline{a})-c(\overline{a}))+(1-x)(p_{2}f(\pi,\overline{a})-c(\overline{a}))$
$\displaystyle\geq
x\cdot\max_{a\in\mathcal{A}}(p_{1}f(\pi,a)-c(a))+(1-x)\cdot\max_{a\in\mathcal{A}}(p_{2}f(\pi,a)-c(a))$

Therefore, it must be the case that $\overline{a}$ is optimal at $p_{1}$ and
$p_{2}$. So $a^{*}$ and $\overline{a}$ have the same Agent utility at $2$
different contracts. But this is a contradiction of Lemma 12. Therefore any
action can be non-uniquely optimal at at most $2$ contracts, the smallest
contract at which it is optimal and the largest contract at which it is
optimal. At $p=0$, the optimal action must be the cheapest action, which by
our assumption is unique. Therefore there is at least one action that is
uniquely optimal at its smallest optimal contract and can only be non-uniquely
optimal at $1$ contract. So the total number of contracts with multiple
optimal actions is at most

$\frac{2(|\mathcal{A}|-1)+1}{2}$

The largest integer value this could be is $|\mathcal{A}|-1$, completing our
proof.

∎

See 4

###### Proof.

Consider any action $a\neq a^{*}$, and the linear contract $\widehat{p}$ such
that $U(a,\widehat{p},\pi)=U(a^{*},\widehat{p},\pi)$. Then,

$\displaystyle\widehat{p}f(\pi,a)-c(a)=\widehat{p}f(\pi,a^{*})-c(a^{*})$
$\displaystyle\Rightarrow\widehat{p}(f(\pi,a)-f(\pi,a^{*}))=c(a)-c(a^{*})$
$\displaystyle\Rightarrow|\widehat{p}(f(\pi,a)-f(\pi,a^{*}))|=|c(a)-c(a^{*})|\geq\Delta_{c}$
$\displaystyle\Rightarrow|f(\pi,a)-f(\pi,a^{*})|\geq\Delta_{c}$

At linear contract $\overline{p}$, the payoff of $a$ is

$\displaystyle U(a,\overline{p},\pi)=\overline{p}f(\pi,a)-c(a)$
$\displaystyle=(\overline{p}-\widehat{p})f(\pi,a)+\widehat{p}f(\pi,a)-c(a)$
$\displaystyle=(\overline{p}-\widehat{p})f(\pi,a)+\widehat{p}f(\pi,a^{*})-c(a^{*})=(\overline{p}-\widehat{p})f(\pi,a)+U(a^{*},\widehat{p},\pi)$
(By the definition of $\widehat{p}$)

Furthermore, we know that

$\displaystyle U(a^{*},\overline{p},\pi)=\overline{p}f(\pi,a^{*})-c(a^{*})$
$\displaystyle=(\overline{p}-\widehat{p})f(\pi,a^{*})+\widehat{p}f(\pi,a^{*})-c(a^{*})=(\overline{p}-\widehat{p})f(\pi,a^{*})+U(a^{*},\widehat{p},\pi)$

Combining these, we get that

$\displaystyle
U(a^{*},\overline{p},\pi)-U(a,\overline{p},\pi)=(\overline{p}-\widehat{p})(f(\pi,a^{*})-f(\pi,a))$
$\displaystyle=|(\overline{p}-\widehat{p})|\cdot|(f(\pi,a^{*})-f(\pi,a))|$ (As
$a^{*}$ is optimal at $\overline{p}$, and thus this difference cannot be
negative) $\displaystyle\geq\beta\cdot\Delta_{c}$

∎

See 5

###### Proof.

Let $a_{1}=\max_{a\in\mathcal{B}(p_{1},\pi,0)}f(\pi,a)$, let
$a_{1,\varepsilon}=\max_{a\in\mathcal{B}(p_{1},\pi,\varepsilon)}f(\pi,a)$ and
let
$a_{2,\varepsilon}=\max_{a\in\mathcal{B}(p_{2},\pi,\varepsilon)}f(\pi,a)$.
Note that $a_{1}$ is the Agent’s exact best response action under $p_{1}$
which is best for the Principal, while $a_{1,\varepsilon}$ and
$a_{2,\varepsilon}$ are the Agent’s $\varepsilon$-approximate best response
actions which are best for the Principal, under their respective policies.
This, we can restate our lemma as proving that for any two linear contracts
$p_{1}$, $p_{2}$ s.t. $p_{1}\geq p_{2}$, $f(\pi,a_{1,\varepsilon})\geq
f(\pi,a_{2,\varepsilon})$.

Assume for contradiction that this is not the case, and
$f(\pi,a_{1,\varepsilon})<f(\pi,a_{2,\varepsilon})$. Then it must be that
$a_{2,\varepsilon}\notin\mathcal{B}(p_{1},\pi,\varepsilon)$, as otherwise we
would have that

$\displaystyle f(\pi,a_{2,\varepsilon})>f(\pi,a_{1,\varepsilon})$
$\displaystyle\geq f(\pi,a_{2,\varepsilon})$ (By the fact that
$a_{2,\varepsilon}\in\mathcal{B}(p_{1},\pi,\varepsilon)$ and
$a_{1,\varepsilon}$ is optimal over all $\mathcal{B}(p_{1},\pi,\varepsilon)$)

This is a contradiction.

As $a_{2,\varepsilon}\notin\mathcal{B}(p_{1},\pi,\varepsilon)$,
$a_{2,\varepsilon}$ is not an $\varepsilon$-approximate best response to
$p_{1}$. So we have that

$\displaystyle
p_{1}f(\pi,a_{1})-c(a_{1})>p_{1}f(\pi,a_{2,\varepsilon})-c(a_{2,\varepsilon})+\varepsilon$
$\displaystyle\Leftrightarrow
c(a_{2,\varepsilon})-c(a_{1})-\varepsilon>p_{1}f(\pi,a_{2,\varepsilon})-f(\pi,a_{1}))$

Furthermore, as $a_{2,\varepsilon}$ is an $\varepsilon$-approximate best
response under $p_{2}$, we have that

$\displaystyle p_{2}f(\pi,a_{1})-c(a_{1})\leq
p_{2}f(\pi,a_{2,\varepsilon})-c(a_{2,\varepsilon})+\varepsilon$
$\displaystyle\Leftrightarrow c(a_{2,\varepsilon})-c(a_{1})-\varepsilon\leq
p_{2}(f(\pi,a_{2,\varepsilon})-f(\pi,a_{1}))$

Finally, we note that

$\displaystyle f(\pi,a_{2,\varepsilon})-f(\pi,a_{1})\geq
f(\pi,a_{2,\varepsilon})-f(\pi,a_{1,\varepsilon})$ (As $a_{1,\varepsilon}$ is
maximizing over a larger set) $\displaystyle>0$ (By our assumption)

Putting these together, we get that

$\displaystyle
p_{2}(f(\pi,a_{2,\varepsilon})-f(\pi,a_{1}))>p_{1}(f(\pi,a_{2,\varepsilon})-f(\pi,a_{1}))$
$\displaystyle\Rightarrow p_{2}>p_{1}$

We have derived a contradiction, completing our proof. ∎

##  Appendix D More Details and Proofs from Section 5.2

###  D.1 Discretization details

Recall the explicit representation of the signal scheme in Eq (6). Note that
each signal scheme selected under our construction of $p^{\prime}$ selects two
strategies in $\mathcal{S}$ and each distribution $p^{\prime}(\cdot|y)$ is
supported only on these two strategies. Now we want to discretize
$p^{\prime}(\cdot|y)$. For some discretization precision $\delta\ll\beta$ with
$\frac{1}{\delta}\in{\mathbb{N}}_{+}$, let $\varphi_{i,j,k_{0},k_{1}}$ for
$i,j\in[n],k_{0},k_{1}\in\\{0,1,\ldots,\frac{1}{\delta}\\}$ represent the
signal scheme with

$\varphi(s_{i}|y=1)=k_{0}\delta\,,\qquad\varphi(s_{i}|y=0)=k_{1}\delta\,.$

Then we let
$\mathcal{P}_{\delta}=\\{\varphi_{i,j,k_{0},k_{1}}|i,j\in[n],k_{0},k_{1}\in\\{0,1,\ldots,\frac{1}{\delta}\\}\\}$
denote the set of all such signal schemes. We have
$\left|\mathcal{P}_{\delta}\right|=\mathcal{O}(\frac{n^{2}}{\delta^{2}})$. We
will return the signal scheme $p_{\delta}(\mu)\in P_{\delta}$ closest to
$p^{\prime}(\mu)$. Recall that our definition of $p^{\prime}(\mu)$ induces a
convex combination of two points in $\text{Ex}^{\prime}$, saying
$\mu=\tau\cdot\mu_{k}^{\prime}+(1-\tau)\cdot\mu^{\prime}_{l}$. Then the
explicit form of $p^{\prime}(\mu)$ is

$\displaystyle p(s_{i_{k}}|y=1)=\frac{\tau\cdot\mu_{k}^{\prime}}{\mu}\,,\quad$
$\displaystyle p(s_{i_{l}}|y=1)=\frac{(1-\tau)\cdot\mu_{l}^{\prime}}{\mu}$
$\displaystyle
p(s_{i_{k}}|y=0)=\frac{\tau\cdot(1-\mu_{k}^{\prime})}{1-\mu}\,,\quad$
$\displaystyle
p(s_{i_{l}}|y=0)=\frac{(1-\tau)\cdot(1-\mu_{l}^{\prime})}{1-\mu}\,.$

By rounding these two probabilities, we obtain a discretized signal scheme
$p_{\delta}(\mu)$ with

$\displaystyle
p_{\delta}(s_{i_{k}}|y=1)=\delta\cdot\operatorname*{arg\,min}_{k\in\\{0,\ldots,1/\delta\\}}\left|k\delta-p(s_{i_{k}}|y=1)\right|\,,$
$\displaystyle
p_{\delta}(s_{i_{k}}|y=0)=\delta\cdot\operatorname*{arg\,min}_{k\in\\{0,\ldots,1/\delta\\}}\left|k\delta-p(s_{i_{k}}|y=0)\right|\,.$

###  D.2 Proofs

For any signal $p$ and any prior distribution $\pi=\mathrm{Ber}(\mu)$, let
$\\{(\tau_{i},\mathrm{Ber}(\mu_{i}))\\}_{i\in[n]}$ denote the induced
distribution of posteriors where
$\tau_{i}=\sum_{y\in\mathcal{Y}}p(s_{i}|y)\pi(y)$ is the probability of the
signal being $s_{i}$ and $\mathrm{Ber}(\mu_{i})$ is the posterior distribution
$\pi(y|s_{i})$ of $y$ given the signal $s_{i}$. Then the expected Principal’s
utility is

$V(a,p,\mu):=\mathbb{E}_{y\sim\mathrm{Ber}(\mu)}\left[V(a,p,y)\right]=\mathbb{E}_{y\sim\mathrm{Ber}(\mu)}\left[\mathbb{E}_{s\sim
p(\cdot|y)}\left[v(a(s),y)\right]\right]=\sum_{i\in[n]}\tau_{i}v(a(s_{i}))\,,$

and the expected Agent’s utility is

$U(a,p,\mu):=\mathbb{E}_{y\sim\mathrm{Ber}(\mu)}\left[U(a,p,y)\right]=\mathbb{E}_{y\sim\mathrm{Ber}(\mu)}\left[\mathbb{E}_{s\sim
p(\cdot|y)}\left[u(a(s),y)\right]\right]=\sum_{i\in[n]}\tau_{i}u(a(s_{i}),\mu_{i})\,.$

Hence, the best response $a^{*}(p,\mu)$ is defined by letting
$a^{*}(p,\mu)(s_{i})=s^{*}(\mu_{i})$ and an action $a$ is an
$\varepsilon$-best response if
$\sum_{i\in[n]}\tau_{i}u(a(s_{i}),\mu_{i})\geq\sum_{i\in[n]}\tau_{i}u(s^{*}(\mu_{i}),\mu_{i})-\varepsilon$.
Then we first introduce the following lemma to prove our results in Bayesian
Persuasion.

######  Lemma 13.

For any $x\in[0,1]$, for any $\mu\in[0,1]$, a signal scheme $p$, which induces
distribution of posteriors as $(\tau,w_{i}),((1-\tau),w_{j})$ with $w_{i}\in
S_{i}$ and $w_{j}\in S_{j}$, is $(x\cdot\eta,x)$-stable under $\mu$ for any
$\eta$ with $[w_{i}-\eta,w_{i}+\eta]\subset S_{i}$ and
$[w_{j}-\eta,w_{j}+\eta]\subset S_{j}$.

###### Proof.

By Assumption 3, each interval has a length of at least $C$. Then for any
$i\in n$ and any $\eta<\frac{C}{2}$, let $S_{i}^{\eta}$ denote the interval
$[\min(S_{i})+\eta,\max(S_{i})-\eta]$ by removing $\eta$ top values and $\eta$
bottom values from the interval $S_{i}$. Then for all $\mu\in S_{i}^{\eta}$,
we have

$\displaystyle u(s_{j},\mu)\leq u(s_{i},\mu)-c_{1}\eta\,,$

for all $j\neq i$. This directly follows from Assumption 3. As mentioned
before, by Assumption 3, there is some minimum difference $c_{1}$ between the
utility slopes $\partial u(s,\cdot)$ of any two strategies. Hence for any
$\mu$ which is $\eta$-far away from an interval edge, we can see that the
Agent utility of every strategy $s_{j}$ other than the optimal strategy
$s_{i}$ at $\mu$ is at least $c_{1}\cdot\eta$ lower. Hence, taking any
strategy other than $s_{i}$ after seeing signal $s_{i}$ would achieve a
utility at least $c_{1}\eta$ lower under $w_{i}$.

If the action $a$ taken by the Agent plays a non-optimal strategy to both
$s_{i}$ and $s_{j}$, it leads to an expected loss for the Agent of
$\geq\tau\cdot c_{1}\eta+(1-\tau)\cdot c_{1}\eta=c_{1}\eta$. More formally,
$U(a,p,\mu)\leq U(a^{*}(p,\mu),p,\mu)-c_{1}\eta$. Thus, for any $x\in[0,1]$,
we have

$\displaystyle U(a,p,\mu)\leq U(a^{*}(p,\mu),p,\mu)-x\cdot c_{1}\eta\,.$

Now consider action $a$ playing one optimal response and one non-optimal
response. W.l.o.g., assume that $a(s_{i})\neq s_{i}$ and $a(s_{j})=s_{j}$.
Then we have

$\displaystyle U(a,p,\mu)$ $\displaystyle\leq U(a^{*}(p,\mu),p,\mu)-\tau
c_{1}\eta\,,$ $\displaystyle V(a,p,\mu)$ $\displaystyle\geq
V(a^{*}(p,\mu),p,\mu)-\tau\,.$

Hence, for any $x\in[0,1]$, if $\tau\leq x$, we have

$\displaystyle V(a,p,\mu)\geq V(a^{*}(p,\mu),p,\mu)-x\,.$

If $\tau>x$, we have

$\displaystyle U(a,p,\mu)\leq U(a^{*}(p,\mu),p,\mu)-x\cdot c_{1}\eta\,.$

By combining the two cases, we have proved the lemma. ∎

####  D.2.1 Proof of Lemma 8

See 8 Before the proof, we first introduce the following lemma.

######  Lemma 14.

For any $\mu\in[0,1]$, we have

$V(a^{*}(p^{\prime}(\mu),\mu),p^{\prime}(\mu),\mu)\geq
V(a^{*}(p,\mu,\varepsilon),p,\mu)-\frac{3\beta}{C}-c_{2}\sqrt{\varepsilon}\,,$

for all $p\in\mathcal{P}$.

###### Proof.

The proof is decomposed to two parts.

  * •

$V(a^{*}(p^{\prime}(\mu),\mu),p^{\prime},\mu)\geq
v^{*}(\mu)-\frac{3\beta}{C}$. (Lemma 15)

  * •

There exists a constant $c_{2}$ such that
$V(a^{*}(p,\mu,\varepsilon),p,\mu)\leq v^{*}(\mu)+c_{2}\sqrt{\varepsilon}$ for
all $p\in\mathcal{P}$. (Lemma 16)

By combining these two parts, we prove Lemma 14.

######  Lemma 15.

For any $\mu\in[0,1]$, we have $V(a^{*}(p^{\prime},\mu),p^{\prime},\mu)\geq
v^{*}(\mu)-\frac{3\beta}{C}$ where $p^{\prime}=p^{\prime}(\mu)$.

###### Proof of Lemma 15.

Recall that the method of finding the optimal achievable Principal’s utility
by Kamenica and Gentzkow [2011], we have
$(\mu,v^{*}(\mu))=\tau(\mu_{i_{j}},v(s_{i_{j}}))+(1-\tau)(\mu_{i_{j+1}},v(s_{i_{j+1}}))$.
Now considering our signal scheme $p^{\prime}$, there are two cases.

##### Case 1

The prior $\mu$ lies in $[\mu_{i_{j}}^{\prime},\mu_{i_{j+1}}^{\prime}]$ with
$\mu=\tau^{\prime}\mu_{i_{j}}^{\prime}+(1-\tau^{\prime})\mu_{i_{j+1}}^{\prime}$.
Recalling our definition of $p^{\prime}$ (where we find the optimal convex
combination of points in $\textrm{Ex}^{\prime}$), we must have

$V(a^{*}(p^{\prime},\mu),p^{\prime},\mu)\geq\tau^{\prime}v(s_{i_{j}})+(1-\tau^{\prime})v(s_{i_{j+1}})\,.$

Since
$\mu=\tau^{\prime}\mu_{i_{j}}^{\prime}+(1-\tau^{\prime})\mu_{i_{j+1}}^{\prime}$
and $\mu=\tau\mu_{i_{j}}+(1-\tau)\mu_{i_{j+1}}$, we have

$\tau(\mu_{i_{j+1}}-\mu_{i_{j}})-\tau^{\prime}(\mu_{i_{j+1}}^{\prime}-\mu_{i_{j}}^{\prime})=\mu_{i_{j+1}}-\mu_{i_{j+1}}^{\prime}\,.$

According to the definition of $\mu^{\prime}$s, we have

$\displaystyle\mu_{i_{j+1}}-\mu_{i_{j}}+2\beta\leq\mu_{i_{j+1}}^{\prime}-\mu_{i_{j}}^{\prime}\leq\mu_{i_{j+1}}-\mu_{i_{j}}+2\beta\,.$

Therefore, we have

$\displaystyle\left|\tau-\tau^{\prime}\right|\leq\frac{\left|\mu_{i_{j+1}}-\mu_{i_{j+1}}^{\prime}\right|+\tau^{\prime}\cdot
2\beta}{\mu_{i_{j+1}}-\mu_{i_{j}}}\,.$

According to Assumption 3 and definition of $\mu^{\prime}$s, we have

$\displaystyle\mu_{i_{j+1}}-\mu_{i_{j}}\geq C\,,$
$\displaystyle\left|\mu_{i_{j+1}}-\mu_{i_{j+1}}^{\prime}\right|\leq\beta\,.$

Hence, we have $\left|\tau-\tau^{\prime}\right|\leq\frac{3\beta}{C}$. Thus, we
have

$\displaystyle V(a^{*}(p^{\prime},\mu),p^{\prime},\mu)\geq$
$\displaystyle\tau^{\prime}v(s_{i_{j}})+(1-\tau^{\prime})v(s_{i_{j+1}})\geq\tau
v(s_{i_{j}})+(1-\tau)v(s_{i_{j+1}})-\frac{3\beta}{C}$ $\displaystyle=$
$\displaystyle v^{*}(\mu)-\frac{3\beta}{C}\,.$

##### Case 2

The prior $\mu$ does not lie in
$[\mu_{i_{j}}^{\prime},\mu_{i_{j+1}}^{\prime}]$. Since
$\mu\in[\mu_{i_{j}},\mu_{i_{j+1}}]$, we have $\mu$ lies in either
$[\mu_{i_{j}},\mu_{i_{j}}^{\prime})$ or
$(\mu_{i_{j+1}}^{\prime},\mu_{i_{j+1}}]$. W.l.o.g., suppose that $\mu$ lies in
$[\mu_{i_{j}},\mu_{i_{j}}^{\prime})$. Then we have
$\left|\mu-\mu_{i_{j}}\right|\leq\beta$ and
$\left|\mu-\mu_{i_{j}}^{\prime}\right|\leq\beta$. Hence we have $\tau\geq
1-\frac{\beta}{C}$ and

$\displaystyle v^{*}(\mu)\leq v(s_{i_{j}})+\frac{\beta}{C}\,.$

Since $\beta<\frac{C}{4}$, we could find a $\tau^{\prime}\in[0,1]$ s.t.
$\mu=(1-\tau^{\prime})\mu_{i_{j-1}}^{\prime}+\tau^{\prime}\mu_{i_{j}}^{\prime}$.
Similarly, we have $\tau^{\prime}\geq 1-\frac{\beta}{C}$ and thus

$\displaystyle
V(a^{*}(p^{\prime},\mu),p^{\prime},\mu)\geq(1-\tau^{\prime})v(s_{i_{j-1}})+\tau^{\prime}v(s_{i_{j}})\geq
v(s_{i_{j}})-\frac{\beta}{C}\,.$

Hence, we have $V(a^{*}(p^{\prime},\mu),p^{\prime},\mu)\geq
v^{*}(\mu)-\frac{2\beta}{C}$. ∎

######  Lemma 16.

There exists a constant $c_{2}$ such that
$V(a^{*}(p,\mu,\varepsilon),p,\mu)\leq v^{*}(\mu)+c_{2}\sqrt{\varepsilon}$ for
all $p\in\mathcal{P}$.

For any $p\in\mathcal{P}$, let
$\\{(\tau_{i},\mathrm{Ber}(w_{i}))\\}_{i\in[n]}$ denote the distribution of
posteriors induced by policy $p$ and prior $\mu$. Let $a$ be any
$\varepsilon$-best response to $(p,\mu)$. Then to prove the lemma, we need to
show that there exists a constant $c_{2}$ such that $V(a,p,\mu)\leq
v^{*}(\mu)+c_{2}\sqrt{\varepsilon}$ for all $p$. We introduce lemmas 17 and 18
to prove Lemma 16.

######  Lemma 17.

For any $\alpha\in[0,c_{1}\cdot C)$, if a strategy $s$ is an
$\alpha$-approximate optimal strategy to $\mu$, i.e.,
$u(s,\mu)=u(s^{*}(\mu),\mu)-\alpha$, then there exists
$\mu^{\prime}\in[\mu-\frac{\alpha}{c_{1}},\mu+\frac{\alpha}{c_{1}}]$ s.t.
$s\in s^{*}(\mu^{\prime})$.

###### Proof.

If $\alpha=0$, then let $\mu^{\prime}=\mu$. Now we consider the case of
$\alpha>0$. We first show that if $s_{i}$ is a best response to $\mu$ and
$s_{i+1}$ is not for some $i\in[n]$, then $s_{i+2}$ cannot be an
$\alpha$-approximate optimal strategy to $\mu$. This is because
$u(s_{i},\mu)-u(s_{i+2},\mu)\geq c_{1}\cdot C$. Therefore, if a strategy $s$
is an $\alpha$-approximate optimal strategy to $\mu$, then $s$ can only be
$s_{i-1}$ or $s_{i+1}$. W.l.o.g., suppose that $s=s_{i+1}$. Let
$\mu^{\prime}=S_{i}\cap S_{i+1}$ be the boundary value s.t. both $s_{i}$ and
$s_{i+1}$ are best response to $\mu^{\prime}$. Then we have $\alpha\geq
c_{1}\left|\mu^{\prime}-\mu\right|$. ∎

######  Lemma 18.

If an action $a$ is an $\varepsilon$-best response to $(p,\mu)$, i.e.,
$\sum_{i\in[n]}\tau_{i}u(a(s_{i}),w_{i})\geq\sum_{i\in[n]}\tau_{i}u(s_{i},w_{i})-\varepsilon$
with $s_{i}\in s^{*}(w_{i})$, then we can find a set of
$\\{w_{i}^{\prime}|i\in[n]\\}$ such that $a(s_{i})\in s^{*}(w_{i}^{\prime})$
and
$\sum_{i\in[n]}\tau_{i}\left|w_{i}-w_{i}^{\prime}\right|\leq\frac{\varepsilon}{c_{1}}(1+\frac{1}{C})$.

###### Proof.

For each $i\in[n]$, if $u(a(s_{i}),w_{i})\geq u(s_{i},w_{i})-c_{1}\cdot C$,
then we can find $w_{i}^{\prime}$ in the way introduced in Lemma 17. Let
$A=\\{i|u(a(s_{i}),w_{i})\geq u(s_{i},w_{i})-c_{1}\cdot C\\}$ denote the
corresponding subset of $i$’s. According to Lemma 17, for all $i\in A$, we
have

$\displaystyle\left|w_{i}-w_{i}^{\prime}\right|\leq\frac{u(s_{i},w_{i})-u(a(s_{i}),w_{i})}{c_{1}}\,.$

For $i\notin A$, we just arbitrarily pick an $w_{i}^{\prime}$ s.t. $a(s_{i})$
is an optimal strategy under $w_{i}^{\prime}$, i.e, $a(s_{i})\in
s^{*}(w_{i}^{\prime})$. Then we have
$u(s_{i},w_{i})-u(a(s_{i}),w_{i})>c_{1}\cdot C$ for all $i\notin A$, and thus

$\varepsilon\geq\sum_{i\notin
A}\tau_{i}\left(u(s_{i},w_{i})-u(a(s_{i}),w_{i})\right)\geq c_{1}\cdot
C\sum_{i\notin A}\tau_{i}\,.$

Therefore, we have $\sum_{i\notin A}\tau_{i}\leq\frac{\varepsilon}{c_{1}C}$.
Then we have

$\sum_{i\in[n]}\tau_{i}\left|w_{i}-w_{i}^{\prime}\right|\leq\frac{1}{c_{1}}\sum_{i\in
A}\tau_{i}(u(s_{i},w_{i})-u(a(s_{i}),w_{i}))+\sum_{i\notin
A}\tau_{i}\leq\frac{\varepsilon}{c_{1}}(1+\frac{1}{C}).$

∎

###### Proof of Lemma 16.

Recall that $\\{(\tau_{i},\mathrm{Ber}(w_{i}))\\}_{i\in[n]}$ is the
distribution of posteriors induced by signal scheme $p$ and prior $\mu$ and
$a$ is an $\varepsilon$-best response to $(p,\mu)$. Now we want to construct
another signal scheme $\varphi$ such that $V(a,p,\mu)\leq
V(a^{*}(\varphi,\mu),\varphi,\mu)+c_{2}\sqrt{\varepsilon}$. Since
$v^{*}(\mu)\geq V(a^{*}(\varphi,\mu),\varphi,\mu)$ due to that $v^{*}(\mu)$ is
the optimal achievable value when the Agent best respond, we prove Lemma 16.

Our goal is to apply the construction in Lemma 18, and construct a
distribution of posteriors with support $\\{w_{i}^{\prime}|i\in[n]\\}$. Since
$\sum_{i\in[n]}\tau_{i}w_{i}^{\prime}\neq\mu$, we need to find an alternative
set of weights $\tau_{i}^{\prime}$’s such that
$\sum_{i\in[n]}\tau_{i}^{\prime}w_{i}^{\prime}=\mu$. According to the
construction in Lemma 17, for those $i$ with $w_{i}^{\prime}\neq w_{i}$,
$w^{\prime}_{i}$ must lie in $[C,1-C]$ since $w_{i}^{\prime}$ always lie on
the boundary of two intervals. Let $B=\\{i|w_{i}^{\prime}\neq w_{i}\\}$. Let
$q=\sum_{i\in[n]}\tau_{i}(w_{i}^{\prime}-w_{i})$. We have

$\sum_{i\in B}\tau_{i}w_{i}^{\prime}=\mu^{\prime}+q\,,$

with $\mu^{\prime}=\mu-\sum_{i\notin B}\tau_{i}w_{i}$. According to Lemma 18,
we have $q\leq\frac{\varepsilon}{c_{1}}(1+\frac{1}{C})$. Let
$\tau_{B}=\sum_{i\in B}\tau_{i}$ denote the probability mass of $i\in B$. Then
there are three cases.

  * •

$\mu^{\prime}<\frac{\varepsilon}{c_{1}C}(1+\frac{1}{C})$. In this case, we
move all probability mass of $\tau_{B}$ to
$w_{n+1}^{\prime}=\frac{\mu^{\prime}}{\tau_{B}}$, which must lie in $[0,1]$ as
$\mu^{\prime}=\sum_{t\in B}\tau_{i}w_{i}$. That is to say, let
$\tau_{i}^{\prime}=0$ for all $i\in B$, $\tau_{i}^{\prime}=\tau_{i}$ for all
$i\notin B$ and $\tau_{n+1}^{\prime}=\tau_{B}$ for
$w_{n+1}^{\prime}=\mu^{\prime}$. Then we have
$\sum_{i=1}^{n+1}\tau_{i}^{\prime}w_{i}^{\prime}=\mu^{\prime}+\sum_{i\notin
B}\tau_{i}w_{i}=\mu$. Thus,
$\\{(\tau_{i}^{\prime},w_{i}^{\prime})|i=1,\ldots,n+1\\}$ is a Bayesian-
plausible distribution of posteriors with $s^{*}(w_{i}^{\prime})=a(s_{i})$ for
all $i\in[n]$.

  * •

$q>0$. we let $\tau_{i}^{\prime}=\frac{\mu^{\prime}\tau_{i}}{\mu^{\prime}+q}$
for $i\in B$, $\tau_{i}^{\prime}=\tau_{i}$ for $i\notin B$, and the remaining
probability mass $\tau_{n+1}^{\prime}=1-\sum_{i\in[n]}\tau_{i}^{\prime}$ on
$w_{n+1}^{\prime}=0$. Then we have
$\sum_{i=0}^{n}\tau_{i}^{\prime}w_{i}^{\prime}=\mu$ and thus,
$\\{(\tau_{i}^{\prime},w_{i}^{\prime})|i=1,\ldots,n+1\\}$ is a Bayesian-
plausible distribution of posteriors with $s^{*}(w_{i}^{\prime})=a(s_{i})$ for
all $i\in[n]$.

  * •

$q<0$ and $\mu^{\prime}\geq\frac{\varepsilon}{c_{1}C}(1+\frac{1}{C})$. Then
let
$\tau_{i}^{\prime}=\frac{(\tau_{B}-\mu^{\prime})\tau_{i}}{\tau_{B}-\mu^{\prime}-q}$
for $i\in B$, $\tau_{i}^{\prime}=\tau_{i}$ for $i\notin B$ and the remaining
probability mass $\tau_{n+1}^{\prime}=1-\sum_{i}\tau_{i}^{\prime}$ on
$w_{n+1}^{\prime}=1$. Note that
$\tau_{B}\geq\frac{1}{1-C}(\mu^{\prime}+q)\geq\mu^{\prime}$ where the first
inequality holds due to $w_{i}^{\prime}\leq 1-C$ for all $i\in B$ and the
second inequality holds due to
$\mu^{\prime}\geq\frac{\varepsilon}{c_{1}C}(1+\frac{1}{C})\geq\frac{|q|}{C}$.
Thus we have $\tau_{i}^{\prime}\geq 0$ and $\tau_{i}$’s define a legal
distribution. Then we have

$\displaystyle\sum_{i\in[n+1]}\tau_{i}^{\prime}w_{i}^{\prime}$
$\displaystyle=\frac{(\tau_{B}-\mu^{\prime})}{\tau_{B}-\mu^{\prime}-q}\sum_{i\in
B}\tau_{i}w_{i}^{\prime}+\sum_{i\notin
B}\tau_{i}w_{i}+(1-\frac{(\tau_{B}-\mu^{\prime})}{\tau_{B}-\mu^{\prime}-q})\tau_{B}$
$\displaystyle=\frac{(\tau_{B}-\mu^{\prime})}{\tau_{B}-\mu^{\prime}-q}(\mu^{\prime}+q)+\sum_{i\notin
B}\tau_{i}w_{i}+(1-\frac{(\tau_{B}-\mu^{\prime})}{\tau_{B}-\mu^{\prime}-q})\tau_{B}$
$\displaystyle=\mu^{\prime}+\sum_{i\notin B}\tau_{i}w_{i}=\mu\,.$

Hence, $\\{(\tau_{i}^{\prime},w_{i}^{\prime})|i=1,\ldots,n+1\\}$ is a
Bayesian-plausible distribution of posteriors with
$s^{*}(w_{i}^{\prime})=a(s_{i})$ for all $i\in[n]$.

Since $w_{i}^{\prime}\in[C,1-C]$ for all $i\in B$, we have
$\mu^{\prime}+q\in[\tau_{B}C,\tau_{B}(1-C)]$. Then in the first case, we have

$\displaystyle V(a,p,\mu)=$
$\displaystyle\sum_{i\in[n]}\tau_{i}v(a(s_{i}))=\sum_{i\notin
B}\tau_{i}v(a(s_{i}))+\tau_{B}v(s^{*}(w_{n+1}^{\prime}))+\sum_{i\in
B}\tau_{i}(v(a(s_{i}))-v(s^{*}(w_{n+1}^{\prime})))$ $\displaystyle\leq$
$\displaystyle\sum_{i\in[n+1]}\tau_{i}^{\prime}v(s^{*}(w_{i}^{\prime}))+\tau_{B}\leq
V(a^{*}(\varphi,\mu),\varphi,\mu)+\frac{2\varepsilon}{c_{1}C^{2}}(1+\frac{1}{C})\,,$

where the last inequality holds due to $\tau_{B}\leq\frac{\mu^{\prime}+q}{C}$.

Since $\mu^{\prime}+q\in[\tau_{B}C,\tau_{B}(1-C)]$, in both of the second case
and the third case, we have
$\tau_{i}\leq(1+\frac{\left|q\right|}{C\tau_{B}-\left|q\right|})\tau_{i}^{\prime}$
for all $i\in B$. Then we have

$\displaystyle V(a,p,\mu)=$
$\displaystyle\sum_{i\in[n]}\tau_{i}v(a(s_{i}))\leq\sum_{i\in
B}(1+\frac{\left|q\right|}{C\tau_{B}-\left|q\right|})\tau_{i}^{\prime}v(a(s_{i}))+\sum_{i\notin
B}\tau_{i}^{\prime}v(a(s_{i}))$ $\displaystyle\leq$
$\displaystyle\sum_{i\in[n]}\tau_{i}^{\prime}v(s^{*}(w_{i}^{\prime}))+\frac{\left|q\right|}{C\tau_{B}-\left|q\right|}=V(a^{*}(\varphi,\mu),\varphi,\mu)+\frac{\left|q\right|}{C\tau_{B}-\left|q\right|}\,,$

and

$\displaystyle V(a,p,\mu)\leq\tau_{B}+\sum_{i\notin
B}\tau_{i}v(a(s_{i}))=\tau_{B}+\sum_{i\notin
B}\tau_{i}^{\prime}v(s^{*}(w_{i}^{\prime}))\leq
V(a^{*}(\varphi,\mu),\varphi,\mu)+\tau_{B}\,.$

Since
$\min(\tau_{B},\frac{\left|q\right|}{C\tau_{B}-\left|q\right|})\leq\sqrt{\frac{\left|q\right|}{C}}+\frac{\left|q\right|}{C}$,
by combining these two inequalities together, we have

$\displaystyle V(a,p,\mu)\leq
V(a^{*}(\varphi,\mu),\varphi,\mu)+\sqrt{\frac{\left|q\right|}{C}}+\frac{\left|q\right|}{C}\leq
V(a^{*}(\varphi,\mu),\varphi,\mu)+2\sqrt{\frac{\varepsilon}{c_{1}C}(1+\frac{1}{C})}\,.$

when $\varepsilon$ is small.

∎

∎

###### Proof of Lemma 8.

According to our definition of $p^{\prime}(\mu)$, it induces a convex
combination of two points in $\text{Ex}^{\prime}$, saying
$\mu=\tau\cdot\mu^{\prime}_{i_{k}}+(1-\tau)\cdot\mu^{\prime}_{i_{l}}$. Recall
that all $\mu$ values associated with points in Ex must be on the boundary
between two intervals. Furthermore, by construction, any point in
$\text{Ex}^{\prime}$ have $\mu^{\prime}$ values which are exactly $\beta$
different from some $\mu$ in Ex. Hence $\mu^{\prime}_{i_{k}}$ and
$\mu^{\prime}_{i_{l}}$ will be at least $\beta$-far from the edge of any
interval. Therefore, Lemma 13 implies that $p^{\prime}(\mu)$ is a $(x\cdot
c_{1}\beta,x)$-stable policy under $\mu$. By combining with Lemma 14, we prove
Lemma 8. ∎

####  D.2.2 Proof of Theorem 4

See 4

###### Proof of Theorem 4.

Recalling our definition of $p^{\prime}(\mu)$, it induces a convex combination
of two points in $\text{Ex}^{\prime}$, saying
$\mu=\tau\cdot\mu^{\prime}_{i_{k}}+(1-\tau)\cdot\mu^{\prime}_{i_{l}}$. Then
the explicit form of $p^{\prime}(\mu)$ is

$\displaystyle p(s_{i_{k}}|y=1)=\frac{\tau\cdot\mu_{k}^{\prime}}{\mu}\,,\quad
p(s_{i_{k}}|y=0)=\frac{\tau\cdot(1-\mu_{k}^{\prime})}{1-\mu}$

By rounding these two probabilities, we obtain a discretized signal scheme
$p_{\delta}(\mu)$ with

$\displaystyle
p_{\delta}(s_{i_{k}}|y=1)=\delta\cdot\operatorname*{arg\,min}_{k\in\\{0,\ldots,1/\delta\\}}\left|k\delta-p(s_{i_{k}}|y=1)\right|\,,\quad
p_{\delta}(s_{i_{k}}|y=0)=\delta\cdot\operatorname*{arg\,min}_{k\in\\{0,\ldots,1/\delta\\}}\left|k\delta-p(s_{i_{k}}|y=0)\right|\,.$

Let $\delta_{1}=p_{\delta}(s_{i_{k}}|y=1)-p^{\prime}(s_{i_{k}}|y=1)$ and
$\delta_{0}=p_{\delta}(s_{i_{k}}|y=0)-p^{\prime}(s_{i_{k}}|y=0)$ denote the
discretization errors with
$\left|\delta_{0}\right|,\left|\delta_{1}\right|<\delta$. We have the new
distribution of posteriors
$(\tau_{\delta},\mu_{\delta,i_{k}}),(1-\tau_{\delta},\mu_{\delta,i_{l}})$ with

$\displaystyle\tau_{\delta}$
$\displaystyle=p_{\delta}(s_{i_{k}}|y=1)\mu+p_{\delta}(s_{i_{k}}|y=0)(1-\mu)=(\frac{\tau\cdot\mu_{i_{k}}^{\prime}}{\mu}+\delta_{1})\mu+(\frac{\tau\cdot(1-\mu_{i_{k}}^{\prime})}{1-\mu}+\delta_{0})(1-\mu)$
$\displaystyle=\tau+\delta_{1}\mu+\delta_{0}(1-\mu)\,,$
$\displaystyle\mu_{\delta,i_{k}}$
$\displaystyle=\pi(y|s_{i,k})=\frac{p_{\delta}(s_{i_{k}}|y=1)\mu}{\tau_{\delta}}=\frac{(\frac{\tau\cdot\mu_{i_{k}}^{\prime}}{\mu}+\delta_{1})\mu}{\tau+\delta_{1}\mu+\delta_{0}(1-\mu)}=\mu_{i_{k}}^{\prime}+\frac{\delta_{1}\mu(1-\mu_{i_{k}}^{\prime})-\delta_{0}(1-\mu)\mu_{i_{k}}^{\prime}}{\tau+\delta_{1}\mu+\delta_{0}(1-\mu)}\,,$
$\displaystyle\mu_{\delta,i_{l}}$
$\displaystyle=\frac{\mu-\tau_{\delta}\mu_{\delta,i_{k}}}{1-\tau_{\delta}}\,.$

Thus, we have $\left|\tau_{\delta}-\tau\right|\leq\delta$ and
$\left|\mu_{\delta,i_{k}}-\mu_{i_{k}}^{\prime}\right|\leq\frac{\delta}{|\tau-\delta|}$.
Due to the symmetry, we have
$\left|\mu_{\delta,i_{l}}-\mu_{i_{l}}^{\prime}\right|\leq\frac{\delta}{|(1-\tau)-\delta|}$.
Then we consider two cases based on the value of $\tau$.

  * •

$\tau<\sqrt{\delta}$ or $\tau>1-\sqrt{\delta}$. W.l.o.g., we assume that
$\tau>1-\sqrt{\delta}$. Then we can show that
$\left|\mu_{\delta,i_{k}}-\mu_{i_{k}}^{\prime}\right|\leq 2\delta$. Then
$p_{\delta}$ is
$((1-\sqrt{\delta})c_{1}(\beta-2\delta),\sqrt{\delta})$-stable. Since
$\mu_{\delta,i_{k}}$ is at least $\beta-2\delta$ way from the edge and if the
Agent chooses the strategy $a(s^{*}(\mu_{\delta,i_{k}}))$ is not
$s^{*}(\mu_{\delta,i_{k}})$ itself given the signal
$s^{*}(\mu_{\delta,i_{k}})$, then

$\displaystyle U(a,p_{\delta},\mu)\leq
U(a^{*}(p_{\delta},\mu),p_{\delta},\mu)-\tau c_{1}(\beta-2\delta)\leq
U(a^{*}(p_{\delta},\mu),p_{\delta},\mu)-(1-\sqrt{\delta})c_{1}(\beta-2\delta)\,.$

If the Agent follows the signal
$a(s^{*}(\mu_{\delta,i_{k}}))=s^{*}(\mu_{\delta,i_{k}})$, then

$\displaystyle V(a,p_{\delta},\mu)\geq
V(a^{*}(p_{\delta},\mu),p_{\delta},\mu)-(1-\tau)\geq
V(a^{*},p_{\delta},\mu)-\sqrt{\delta}\,.$

And also, since $\left|\mu_{\delta,i_{k}}-\mu_{i_{k}}^{\prime}\right|\leq
2\delta$, we have $s^{*}(\mu_{\delta,i_{k}})=s^{*}(\mu_{i_{k}}^{\prime})$.
Thus, we have

$\displaystyle V(a^{*}(p_{\delta},\mu),p_{\delta},\mu)$ $\displaystyle=$
$\displaystyle\tau_{\delta}v(s^{*}(\mu_{\delta,i_{k}}))+(1-\tau_{\delta})v(s^{*}(\mu_{\delta,i_{l}}))$
$\displaystyle=$
$\displaystyle\tau_{\delta}v(s^{*}(\mu_{i_{k}}^{\prime}))+(1-\tau_{\delta})v(s^{*}(\mu_{\delta,i_{l}}))$
$\displaystyle\geq$ $\displaystyle\tau_{\delta}v(s^{*}(\mu_{i_{k}}^{\prime}))$
$\displaystyle\geq$ $\displaystyle(\tau-\delta)v(s^{*}(\mu_{i_{k}}^{\prime}))$
$\displaystyle\geq$ $\displaystyle
V(a^{*}(p^{\prime}(\mu),\mu),p^{\prime}(\mu),\mu)-(1-\tau)-\delta$
$\displaystyle\geq$ $\displaystyle
V(a^{*}(p^{\prime}(\mu),\mu),p^{\prime}(\mu),\mu)-2\sqrt{\delta}$

  * •

$\tau\in[\sqrt{\delta},1-\sqrt{\delta}]$. Then both
$\left|\mu_{\delta,i_{k}}-\mu_{i_{k}}^{\prime}\right|\leq 2\sqrt{\delta}$ and
$\left|\mu_{\delta,i_{l}}-\mu_{i_{l}}^{\prime}\right|\leq 2\sqrt{\delta}$. Let
$\sqrt{\delta}<\frac{\beta}{4}$. Then by Lemma 13, we have that $p_{\delta}$
is $(x\cdot c_{1}\beta/2,x)$-stable for any $x\in[0,1]$. Since
$s^{*}(\mu_{\delta,i_{k}})=s^{*}(\mu_{i_{k}}^{\prime})$ and
$s^{*}(\mu_{\delta,i_{l}})=s^{*}(\mu_{i_{l}}^{\prime})$, we have

$\displaystyle V(a^{*},p_{\delta},\mu)=V(a^{*},p^{\prime}(\mu),\mu).$

Hence, $p_{\delta}(\mu)$ is a
$(\frac{3\beta}{C}+c_{2}\sqrt{\varepsilon}+2\sqrt{\delta},\varepsilon,x\cdot
c_{1}\beta/2,\max(x,\sqrt{\delta}))$-optimal stable policy under $\mu$ for any
$x\in[0,1]$. ∎

####  D.2.3 Proof of Lemma 6

See 6

###### Proof.

This is because for each strategy $s\in\mathcal{S}$, there exists
$\mu_{s}\in[0,1]$ and $c_{S}>0$ such that
$u(s,\mu_{s})\geq\mu(s^{\prime},\mu_{s})+C_{s}$ for all $s^{\prime}\neq s$ in
$\mathcal{S}$. Hence for all
$\mu\in(\mu_{s}-\frac{C_{s}}{2},\mu_{s}+\frac{C_{s}}{2})$, we have
$u(s,\mu)\geq
u(s,\mu_{s})-\frac{C_{s}}{2}\geq\mu(s^{\prime},\mu_{s})+\frac{C_{s}}{2}\geq
u(s^{\prime},\mu)$, where the first and the last inequalities follow from the
fact that $u(s,\cdot)$ is a linear function with $\left|\partial
u(s,\cdot)\right|\leq 1$. Let $C=\min_{s\in\mathcal{S}}C_{s}$ denote the
minimal width of the intervals in $\\{S_{1},\ldots,S_{n}\\}$ observe that
since each $C_{s}>0$, $C>0$.

Note that Assumption 3 also implies that, for any two different strategies
$s,s^{\prime}$, the slopes of $u(s,\cdot)$ and $u(s^{\prime},\cdot)$, denoted
by $\partial u(s,\cdot)$ and $\partial u(s^{\prime},\cdot)$, are different.
Otherwise, one of the strategies is dominated by the other one and cannot be
strictly optimal at any prior $\mu$, which conflicts with Assumption 3. ∎

##  Appendix E Proofs from Section 6

###  E.1 Proof of Lemma 9

See 9

###### Proof.

When Assumption 2 holds, we have

$\frac{1}{n_{p,r}}\mathbb{E}_{a_{1:T}}\left[\left|\sum_{t\in(p,r)}U(a_{t},p,y_{t})-U(\widehat{\mu}_{p,r},p,y_{t})\right|\right]\leq\mathcal{O}\left(\frac{1}{\sqrt{n_{p,r}}}\right)\,,$

and

$\frac{1}{n^{p_{0}}_{r}}\mathbb{E}_{a^{p_{0}}_{1:T}}\left[\left|\sum_{t:r_{t}=r}U(a_{t}^{p_{0}},p,y_{t})-U(\widehat{\mu}^{p_{0}}_{r},p,y_{t})\right|\right]\leq\mathcal{O}\left(\frac{1}{\sqrt{n^{p_{0}}_{r}}}\right)\,.$

This directly implies the following.

$\displaystyle\textrm{NegReg}(y_{1:T},p_{1:T}^{\sigma},r^{\sigma}_{1:T})$
$\displaystyle=$
$\displaystyle\frac{1}{T}\mathbb{E}_{a_{1:T}}\left[\sum_{t=1}^{T}U(a_{t},p_{t},y_{t})-\max_{h:\mathcal{P}_{0}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T}U(h(p_{t},r_{t}),p_{t},y_{t})\right]$
$\displaystyle\leq$
$\displaystyle\frac{1}{T}\mathbb{E}_{a_{1:T}}\left[\sum_{(p,r)\in\mathcal{P}_{\mathcal{O}}\times\mathcal{A}}\left(\sum_{t\in(p,r)}U(\widehat{\mu}_{p,r},p,y_{t})-\max_{a\in\mathcal{A}}\sum_{t\in(p,r)}U(a,p,y_{t})\right)\right]+\mathcal{O}(\sqrt{\left|\mathcal{P}^{\prime}\right|\left|\mathcal{A}\right|/T})$
$\displaystyle\leq$
$\displaystyle\mathcal{O}(\sqrt{\left|\mathcal{P}^{\prime}\right|\left|\mathcal{A}\right|/T})\,.$

Similarly, we have
$\textrm{NegReg}(y_{1:T},(p_{0},\ldots,p_{0}),r^{p_{0}}_{1:T})\leq\mathcal{O}(\sqrt{\left|\mathcal{A}\right|/T})$
. ∎

###  E.2 Proof of Lemma 10

See 10

###### Proof of Lemma 10.

For proposed mechanism $\sigma^{\dagger}$, let $t\in(p,r)$ denote
$t:(p_{t},r_{t})=(p,r)$. Let $n_{p,r}=\sum_{t=1}^{T}\mathds{1}[t\in(p,r)]$
denote the number of rounds in which $(p_{t},r_{t})=(p,r)$. Let
$\widehat{y}_{p,r}=\frac{1}{n_{p,r}}\sum_{t\in(p,r)}y_{t}$ denote the
empirical distribution of states in these rounds and
$\pi_{p,r}=\frac{1}{n_{p,r}}\sum_{t\in(p,r)}\pi_{t}$ denote the empirical
distribution of the forecasts. For constant mechanism $\sigma^{p_{0}}$, let
$t\in(r)$ denote $t:r^{p_{0}}_{t}=r$. Let
$\mathcal{E}_{3,p_{0}}=\\{\mathds{1}[a^{*}(p_{0},\pi_{t})=a]\\}_{a\in\mathcal{A}}$.
Let $\alpha(\mathcal{E}_{3,p_{0}})=\sum_{E\in\mathcal{E}_{3,p_{0}}}\alpha(E)$
and $\alpha(\mathcal{E}_{4})=\sum_{E\in\mathcal{E}_{4}}\alpha(E)$. For any
$p_{0}\in\mathcal{P}_{0}$, we have

$\displaystyle\sum_{t=1}^{T}V(r_{t},p_{t},y_{t})$ $\displaystyle=$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}\sum_{t\in(p,r)}V(r,p,y_{t})$
$\displaystyle=$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}n_{p,r}V(r,p,\widehat{y}_{p,r})$
$\displaystyle\geq$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}n_{p,r}V(r,p,\pi_{p,r})-\alpha(\mathcal{E}_{4})T$
($\mathcal{E}_{4}$-bias) $\displaystyle=$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}\sum_{t\in(p,r)}V(a^{*}(p,\pi_{t}),p,\pi_{t})-\alpha(\mathcal{E}_{4})T$
(since $r_{t}=a^{*}(p,\pi_{t})$) $\displaystyle=$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}\sum_{t\in(p,r)}\max_{p^{\prime}\in\mathcal{P}_{0}}V(a^{*}(p^{\prime},\pi_{t}),p^{\prime},\pi_{t})-\alpha(\mathcal{E}_{4})T$
(since $p_{t}=p^{*}(\pi_{t})$) $\displaystyle\geq$
$\displaystyle\sum_{t=1}^{T}V(a^{*}(p_{0},\pi_{t}),p_{0},\pi_{t})-\alpha(\mathcal{E}_{4})T$
$\displaystyle=$
$\displaystyle\sum_{r}\sum_{t\in(r)}V(r,p_{0},\pi_{t})-\alpha(\mathcal{E}_{4})T$
$\displaystyle\geq$
$\displaystyle\sum_{r}\sum_{t\in(r)}V(r,p_{0},y_{t})-\alpha(\mathcal{E}_{3,p_{0}})T-\alpha(\mathcal{E}_{4})T$
($\mathcal{E}_{3}$-bias) $\displaystyle=$
$\displaystyle\sum_{t=1}^{T}V(r^{p_{0}}_{t},p_{0},y_{t})-\alpha(\mathcal{E}_{3,p_{0}})T-\alpha(\mathcal{E}_{4})T\,.$

According to Theorem 1, we have
$\alpha(\mathcal{E}_{3,p_{0}})=\widetilde{\mathcal{O}}(\left|\mathcal{Y}\right|\sqrt{\left|\mathcal{A}\right|/T})$
and
$\alpha(\mathcal{E}_{4})=\widetilde{\mathcal{O}}(\left|\mathcal{Y}\right|\sqrt{\left|\mathcal{P}_{0}\right|\left|\mathcal{A}\right|/T})$.
Then we are done with the proof. ∎

###  E.3 Proof of Lemma 11

See 11

###### Proof of Lemma 11.

For the proposed mechanism $\sigma^{\dagger}$, let

$\textrm{SwapReg}^{\dagger}_{p,r}=\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t\in(p,r)}\left(U(h(a_{t}),p_{t},y_{t})-U(a_{t},p_{t},y_{t})\right)$

denote the contextual swap regret for the Agent over the subsequence in which
$(p_{t},r_{t})=(p,r)$. Similarly, for the fixed mechanism $\sigma^{p_{0}}$,
let

$\textrm{SwapReg}^{p_{0}}_{r}=\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t\in(r)}\left(U(h(a^{p_{0}}_{t}),p_{0},y_{t})-U(a^{p_{0}}_{t},{p_{0}},y_{t})\right)$

denote the contextual swap regret for the Agent over the subsequence in which
$r^{p_{0}}_{t}=r$.

Similarly, let

$\textrm{NegReg}^{\dagger}_{p,r}=\sum_{t\in(p,r)}U(a_{t},p_{t},y_{t})-\max_{a\in\mathcal{A}}\sum_{t\in(p,r)}U(a,p_{t},y_{t})$

and

$\textrm{NegReg}^{p_{0}}_{r}=\sum_{t\in(r)}U(a^{p_{0}}_{t},p_{0},y_{t})-\max_{a\in\mathcal{A}}\sum_{t\in(r)}U(a,{p_{0}},y_{t})$

denote the negative cross swap regrets for the Agent over the subsequence in
which $(p_{t},r_{t})=(p,r)$ under the proposed mechanism $\sigma^{\dagger}$
and the subsequence in which $r^{p_{0}}_{t}=r$ under the constant mechanism
$\sigma^{p_{0}}$ respectively. For proposed mechanism $\sigma^{\dagger}$, let
$t\in(p,r,a)$ denote $t:(p_{t},r_{t},a_{t})=(p,r,a)$. For constant mechanism
$\sigma^{p_{0}}$, let $t\in(r,a)$ denote
$t:(r^{p_{0}}_{t},a^{p_{0}}_{t})=(r,a)$. We have

$\displaystyle\textrm{UGap}(y_{1:T},p^{\sigma}_{1:T},r^{\sigma}_{1:T},a^{\sigma}_{1:T})$
$\displaystyle=$
$\displaystyle\max_{h:\mathcal{P}_{0}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\min_{h^{\prime}:\mathcal{P}_{0}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T}(U(h(p_{t},r_{t},a_{t}),p_{t},y_{t})-U(h^{\prime}(p_{t},r_{t}),p_{t},y_{t}))$
$\displaystyle=$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}\left(\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t\in(p,r)}(U(h(a_{t}),p,y_{t})-U(a_{t},p,y_{t}))+\min_{r^{\prime}\in\mathcal{A}}\sum_{t\in(p,r)}(U(a_{t},p,y_{t})-U(r^{\prime},p,y_{t}))\right)$
$\displaystyle=$
$\displaystyle\sum_{(p,r)\in\mathcal{P}_{0}\times\mathcal{A}}\textrm{SwapReg}^{\dagger}_{p,r}+\textrm{NegReg}^{\dagger}_{p,r}\,.$

Similarly, for constant mechanism $\sigma^{p_{0}}$, we have

$\textrm{UGap}(y_{1:T},(p_{0},\ldots,p_{0}),r^{p_{0}}_{1:T},a^{p_{0}}_{1:T})=\sum_{r\in\mathcal{A}}\textrm{SwapReg}^{p_{0}}_{r}+\textrm{NegReg}^{p_{0}}_{r}\,.$

According to Assumption 4, we have

$\frac{1}{T}\sum_{t=1}^{T}(V(r_{t},p_{t},y_{t})-V(a_{t},p_{t},y_{t}))\leq
M_{1}\cdot\textrm{UGap}(y_{1:T},p_{1:T},r_{1:T},a_{1:T})+M_{2}\,.$

Therefore,

$\displaystyle\mathbb{E}_{a_{1:T}}\left[\frac{1}{T}\sum_{t=1}^{T}V(a_{t},p_{t},y_{t})\right]\geq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(r_{t},p_{t},y_{t})-M_{1}\cdot\mathbb{E}_{a_{1:T}}\left[\textrm{UGap}(y_{1:T},p^{\sigma}_{1:T},r^{\sigma}_{1:T},a^{\sigma}_{1:T})\right]-M_{2}$
$\displaystyle\geq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(r_{t},p_{t},y_{t})-M_{1}(\varepsilon_{\textrm{swap}}+\varepsilon_{\textrm{neg}})-M_{2}\,,$

and

$\displaystyle\mathbb{E}_{a^{p_{0}}_{1:T}}\left[\frac{1}{T}\sum_{t=1}^{T}V(a_{t}^{p_{0}},p_{0},y_{t})\right]\leq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(r^{p_{0}}_{t},p_{0},y_{t})+M_{1}\cdot\mathbb{E}_{a^{p_{0}}_{1:T}}\left[\textrm{UGap}(y_{1:T},(p_{0},\ldots,p_{0}),r^{p_{0}}_{1:T},a^{p_{0}}_{1:T})\right]+M_{2}$
$\displaystyle\leq$
$\displaystyle\frac{1}{T}\sum_{t=1}^{T}V(r^{p_{0}}_{t},p_{0},y_{t})+M_{1}(\varepsilon_{\textrm{swap}}+\varepsilon_{\textrm{neg}})+M_{2}\,.$

∎

##  Appendix F Proofs from Section 7

See 2

###### Proof.

Consider the following contract setting: there are two actions the Agent can
take, $a_{1}$ and $a_{2}$. $a_{1}$ gives the Principal a value of $1$, and
$a_{2}$ gives her a value of $2$. The cost of $a_{1}$ for the Agent is
$\frac{1}{4}$, and the cost of $a_{2}$ is $\frac{1}{2}$. The Principal’s
contract space has only two linear contracts, $p_{1}=\frac{1}{4}$ and
$p_{2}=\frac{1}{2}$. Thus, $p_{1}$ equally incentivizes $a_{1}$ and $a_{2}$,
while $p_{2}$ strictly incentivizes $a_{2}$.

Intuitively, we will show that $p_{1}$ is not stable, as the Agent could
tiebreak in favor of $a_{1}$ instead of $a_{2}$ and significantly decrease the
Principal’s payoff. Furthermore, $p_{2}$ is not optimal, as if the Agent were
tiebreaking in favor of $a_{2}$, the Principal would have rather played
$p_{1}$. We formalize this below.

Note that the payoffs for the Principal and Agent are independent of the state
of nature, and thus of the prior $\pi$. Furthermore, $a^{*}(p_{1},\pi)=a_{2}$,
and $a^{*}(p_{1},\pi)=a_{2}$, $\forall\pi$. Let us first assume for
contradiction that $p_{1}$ is a $(\beta,\gamma)$-stable optimal policy where
$\gamma=o(1)$ and $\beta>0$. This means that either

$U(a,p_{1},\pi)\leq U(a^{*}(p_{1},\pi),p_{1},\pi)-\beta$

or

$V(a,p_{1},\pi)\geq V(a^{*}(p_{1},\pi),p_{1},\pi)-\gamma$

For the first condition, we get that

$\displaystyle U(a_{1},p_{1},\pi)\leq U(a_{2},p_{1},\pi)-\beta$
$\displaystyle\Rightarrow p_{1}f(a_{1})-c(a_{1})\leq
p_{2}f(a_{1})-c(a_{2})-\beta$
$\displaystyle\Rightarrow\frac{1}{4}-\frac{1}{4}\leq\frac{1}{2}-\frac{1}{2}-\beta$
$\displaystyle\Rightarrow\beta\leq 0$

This derives a contradiction, so the second condition must be satisfied.

For the second condition, we get that

$\displaystyle V(a_{1},p_{1},\pi)\geq V(a_{2},p_{1},\pi)-\gamma$
$\displaystyle\Rightarrow(1-\frac{1}{4})\cdot 1\geq(1-\frac{1}{4})\cdot
2-\gamma$ $\displaystyle\Rightarrow\gamma\geq\frac{3}{4}$

This also derives a contradiction. Therefore neither condition is satisfied,
so $p_{1}$ is not a $(c,\varepsilon,\beta,\gamma)$-stable optimal policy for
any $\gamma=o(1)$ and $\beta>0$.

Next, consider $p_{2}$. Let us assume for contradiction that $p_{2}$ is a
$(c,\varepsilon,\beta,\gamma)$-stable optimal policy where $c=o(1)$ and
$\varepsilon=0$.

Then,

$\displaystyle V(a^{*}(p_{2},\pi),p_{2},\pi)\geq
V(a^{*}(p_{1},\pi,0),p_{1},\pi)-c$ $\displaystyle\Rightarrow
V(a_{2},p_{2},\pi)\geq V(a_{2},p_{1},\pi)-c$ $\displaystyle\Rightarrow
1\geq\frac{3}{2}-c$ $\displaystyle\Rightarrow c\geq\frac{1}{2}$

This derives a contradiction.

As neither $p_{1}$ nor $p_{2}$ are $(c,\varepsilon,\beta,\gamma)$-stable
optimal policies for $c=o(1)$, $\varepsilon\geq 0$, $\beta>0$ and
$\gamma=o(1)$, this completes our proof. ∎

See 1

See 3

We will prove these propositions in conjunction. Our proof assumes the
existence of and makes use of the learning algorithm $\mathcal{L}^{*}$, and we
derive results for both propositions, depending on which guarantees
$\mathcal{L}^{*}$ has.

###### Proof.

Consider a repeated linear contracting problem with two states of nature, $M$
and $H$, and let the realized state sequence be $y_{1:T}$. The Agent’s per-
round action space is $\mathcal{A}=\\{work,shirk\\}$. The Principal’s per-
round policy space is discretized according to
$\mathcal{P}_{\delta}=\\{0,\delta,2\delta,\ldots,\left\lfloor\frac{1}{\delta}\right\rfloor\delta\\}$,
the set of all $\delta$-discretized linear contracts. We assume $\delta$ is
such that $0.5,0.6\in\mathcal{P}_{\delta}$. If the state of nature in a given
round is $M$, the task will be completed if and only if the Agent plays
$work$. If the state of nature is $H$, the task will not be completed
regardless. The Principal gets payoff $2$ if the task is completed. It costs
the Agent $0$ to shirk and $1$ to work.

For any mechanism $\sigma$, we will construct an algorithm $\mathcal{L}$ for
the Agent that gives the Principal high regret. Unlike standard learning
algorithms, $\mathcal{L}$ has access to the entire state sequence. Towards
defining this algorithm, we will first define two simpler algorithms that will
be used as a subroutines which use knowledge of $y_{2:T}$. We will call these
algorithms $a^{*}$ and $b^{*}$.

$a^{*}$ plays $work$ if $y_{t}=M$ and $shirk$ if $y_{t}=H$.

$b^{*}$ plays $work$ if $y_{t}=M$ and plays $shirk$ w.p. $\frac{4}{5}$ and
$work$ w.p. $\frac{1}{5}$ if $y_{t}=H$.

Furthermore, let us pick an algorithm which always achieves sublinear
Contextual Swap Regret for all states of nature sequences against $\sigma$,
and call it $noreg$. We know that $noreg$ must exist, by our assumption that
some $\mathcal{L}^{*}$ exists. If there is a learning algorithms in this
setting which achieve sublinear negative regret for all sequences against
$\sigma$, we will pick such an algorithm. For some $y_{1:T}$, let $m_{y,t}$ be
the number of medium states seen in the first $t$ rounds. Let
$balanced_{t}=true$ if, on round $t$,
$|m_{m,t}-m_{h,t}|\leq\sqrt{12T\ln\left(2\left(1+\log_{2}\left(T\right)\right)^{2}\right)}$.
Furthermore, let $balanced_{all}$ be the event that $balanced_{t}=true$ for
all $t\leq T$. Intuitively, this condition checks whether the history of
nature states is roughly balanced between $M$ and $H$ at each round.

We are finally ready to define $\mathcal{L}$. This algorithm uses $a^{*}$,
$b^{*}$, $noreg$ and $balanced_{t}$ to exploit knowledge about the states of
nature fully, but does so deliberately imperfectly so as not to incur negative
regret.

In $\mathcal{L}$, if the very first state of nature of $y$ is $M$, then
$\mathcal{L}$ plays $a^{*}$ until the Principal ever plays a contract which is
not $(0.5,r_{t}=work)$, and then it plays $noreg$ for the rest of the game. If
the very first state of nature of $y$ is $H$, then it plays $b^{*}$ until the
Principal ever plays a contract which is not $(0.6,r_{t}=work)$, and then it
plays $noreg$ for the rest of the game. Furthermore, if the state sequence
ever invalidates the balanced condition, the algorithm immediately begins
playing $noreg$ for the rest of the game.

Algorithm 5 $\mathcal{L}$

$t\leftarrow 1$

Play $shirk$ on the first round

Observe $y_{1}$

$t\leftarrow 2$

if $y_{1}=M$ then

$\overline{p}\leftarrow 0.5$

$alg\leftarrow a^{*}$

else

$\overline{p}\leftarrow 0.6$

$alg\leftarrow b^{*}$

end if

while $(t\leq T)$, $(p_{t}=\overline{p})$, $(r_{t}=work)$ and $balanced_{t}$
do

Play according to $alg$

$t\leftarrow t+1$

end while

while $(t\leq T)$ do

Play $noreg$ with the entire history of play in mind

$t\leftarrow t+1$

end while

The intuition is as follows: if the number of $M$ and $H$ states is
approximately equal, the Principal gets a higher payoff when the Agent plays
according to $a^{*}$ or $b^{*}$ than when he plays according to $noreg$. But
the Agent himself is roughly indifferent between these algorithms. Therefore
if the Principal’s mechanism causes $noreg$ to be played when $a^{*}$ or
$b^{*}$ could have been played, the Principal will have non-vanishing policy
regret. Of course, if the number of $M$ and $H$ states is not approximately
equal, there is no guarantee on the performance of $a^{*}$ or $b^{*}$.
However, if this is ever the case, $\mathcal{L}$ will switch to playing
$noreg$ to ensure that it continues to satisfy the assumptions on its
performance.

We prove that $\mathcal{L}$ ensures the Principal high regret in Lemma 19. To
do this, we introduce a distribution $y^{*}$ which is i.i.d. between $M$ and
$H$ in each round. We use the fact that, in expectation over $y^{*}$, the
Principal payoff under $noreg$ is $o(T)$, and the Principal payoff when the
Agent is playing either $a^{*}$ or $b^{*}$ is $\Omega(T)$ (Lemma 25). This
implies that there is at least one sequence under which this difference is
realized, or in other words, there is a sequence where the Principal has
significant regret when $noreg$ is played rather than $a^{*}$ or $b^{*}$. The
final piece we need is that such a sequence exists where $balanced_{all}$ is
satisfied, in order that the Agent is actually playing $a^{*}$ or $b^{*}$.
Because the probability of a sequence from $y^{*}$ not satisfying the balanced
condition approaches $0$ with $T$ (Lemma 23), we can show that such a sequence
must exist.

Next, we turn to proving that $\mathcal{L}$ has vanishing Contextual Swap
regret in Lemma 20. Towards this, use the fact that if $balanced_{all}$ is
true and the Principal is playing in a way that causes the Agent to play
$a^{*}$ or $b^{*}$, $a^{*}$ and $b^{*}$ have bounded swap regret (Lemma 26).
We use this with the fact that $\mathcal{L}$ switches to playing $noreg$ when
either $balanced_{all}$ is not true or the Principal misbehaves to show that
$\mathcal{L}$ always has vanishing swap regret. Combining Lemmas 19 and 20
completes the proof of Proposition 1.

Finally, in the case where $noreg$ also has bounded negative regret, we show
in Lemma 21 that $\mathcal{L}$ has bounded negative regret as well, completing
the proof of Proposition 3. ∎

######  Lemma 19.

For any Principal mechanism, there is a sequence of states of nature such that
$\mathcal{L}$ will ensure the Principal non-vanishing policy regret.

###### Proof.

Consider any Principal mechanism $\sigma$. On round $t=1$, before observing
any information about the nature states, the mechanism must provide the first
policy. There are two cases:

  * •

The mechanism provides the contract $0.5$ and the recommendation $work$
$w.p.\leq\frac{1}{2}$. Then, we will evaluate the expected regret of $\sigma$
over the distribution of nature states which begin with $y_{1}=M$ and then are
distributed according to $y^{*}_{2:T}$. In the first round, with probability
at least $\frac{1}{2}$, the Agent immediately begins playing $noreg$.
Alternately, if the Principal had played $(0.5,work)$ in the first round (and
throughout the entire game), the Agent would have played $a^{*}$. We can
compute the regret of the Principal to this alternate policy sequence, in
expectation over $y^{*}_{2:T}$.

$\displaystyle\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})]-\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle=\mathbb{P}(balanced_{all})\mathbb{E}_{y_{2:T}^{*},\mathcal{L}}[\sum_{t=1}^{T}V(\mathcal{L},(0.5,work),y_{t})|balanced_{all}]$
$\displaystyle+\mathbb{P}(\neg
balanced_{all})\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|\neg
balanced_{all}]-\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle\geq\frac{3}{4}\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]-\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By Lemma 23)
$\displaystyle\geq\frac{3}{4}\mathbb{E}_{y_{2:T}^{*},a^{*},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]$
$\displaystyle-\mathbb{P}(\sigma_{1}\neq(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=1}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle-\mathbb{P}(\sigma_{1}=(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle\geq\frac{3}{4}\mathbb{E}_{y_{2:T}^{*},a^{*},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})]-o(T)$
$\displaystyle-\mathbb{P}(\sigma_{1}\neq(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=1}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle-\mathbb{P}(\sigma_{1}=(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By Lemma 22)
$\displaystyle=\frac{3}{4}(\frac{T}{2}-\frac{1}{2}\cdot\frac{T}{2})-\mathbb{P}(\sigma_{1}\neq(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=1}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle-\mathbb{P}(\sigma_{1}=(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By the definition of $a^{*}$ over $y^{*}$)
$\displaystyle=\frac{3}{4}\cdot\frac{T}{4}-\mathbb{P}(\sigma_{1}\neq(0.5,work))\cdot
o(T)-\mathbb{P}(\sigma_{1}=(0.5,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By Lemma 24)
$\displaystyle\geq\frac{3}{4}\cdot\frac{T}{4}-\mathbb{P}(\sigma_{1}\neq(0.5,work))\cdot
o(T)-\mathbb{P}(\sigma_{1}=(0.5,work))\cdot(\frac{T}{4}+o(T))$ (By Lemma 25)
$\displaystyle\geq\frac{3}{4}\cdot\frac{T}{4}-\frac{1}{2}\cdot
o(T)-\frac{1}{2}\cdot(\frac{T}{4}+o(T))=\frac{3T}{16}-\frac{T}{8}-o(T)$
$\displaystyle=\Omega(T)$

The expected total regret over this distribution of sequences against
$\mathcal{L}$ is $\Omega(T)$. Therefore, there must be at least one sequence
beginning with $M$ that has regret of $\Omega(T)$.

  * •

The mechanism provides the contract $0.6$ and the recommendation $work$ w.p.
$\leq\frac{1}{2}$. Then, we will evaluate the expected regret of $\sigma$ over
the distribution of nature states which begin with $y_{1}=H$ and then are
distributed according to $y^{*}_{2:T}$. There is at least a $\frac{1}{2}$
probability that after the first round, the Agent immediately begins playing
$noreg$. Alternately, if the Principal had played $(0.6,work)$ in the first
round (and throughout the entire game), the Agent would have played $b^{*}$.
We can compute the regret of the Principal to this alternate policy sequence,
in expectation over $y^{*}_{2:T}$:

$\displaystyle\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.6,work),y_{t})]-\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle=\mathbb{P}(balanced_{all})\mathbb{E}_{y_{2:T}^{*},\mathcal{L}}[\sum_{t=1}^{T}V(\mathcal{L},(0.6,work),y_{t})|balanced_{all}]$
$\displaystyle+\mathbb{P}(\neg
balanced_{all})\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.6,work),y_{t})|\neg
balanced_{all}]-\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle\geq\frac{3}{4}\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.6,work),y_{t})|balanced_{all}]-\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By Lemma 23)
$\displaystyle\geq\frac{3}{4}\mathbb{E}_{y_{2:T}^{*},b^{*},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.6,work),y_{t})|balanced_{all}]$
$\displaystyle-\mathbb{P}(\sigma_{1}\neq(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=1}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle-\mathbb{P}(\sigma_{1}=(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle\geq\frac{3}{4}\mathbb{E}_{y_{2:T}^{*},b^{*},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.6,work),y_{t})]-o(T)$
$\displaystyle-\mathbb{P}(\sigma_{1}\neq(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=1}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle-\mathbb{P}(\sigma_{1}=(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By Lemma 22)
$\displaystyle=\frac{3}{4}(\frac{T}{5})-\mathbb{P}(\sigma_{1}\neq(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=1}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle-\mathbb{P}(\sigma_{1}=(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By the definition of $b^{*}$ over $y^{*}$)
$\displaystyle=\frac{3}{4}\cdot\frac{T}{5}-\mathbb{P}(\sigma_{1}\neq(0.6,work))\cdot
o(T)-\mathbb{P}(\sigma_{1}=(0.6,work))\cdot\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
(By Lemma 24)
$\displaystyle\geq\frac{3T}{20}-\mathbb{P}(\sigma_{1}\neq(0.6,work))\cdot
o(T)-\mathbb{P}(\sigma_{1}=(0.6,work))\cdot(\frac{T}{4}+o(T))$ (By Lemma 25)
$\displaystyle\geq\frac{3T}{20}-\frac{1}{2}\cdot
o(T)-\frac{1}{2}\cdot(\frac{T}{4}+o(T))=\frac{3T}{20}-\frac{T}{8}-o(T)$
$\displaystyle=\Omega(T)$

For an equivalent argument to the first case, there must be at least one
sequence beginning with $H$ that has regret of $\Omega(T)$

∎

Next, we show that these learning algorithm which can guarantee the Principal
non-vanishing policy regret also satisfies our assumption that the Agent
achieves no swap regret.

######  Lemma 20.

$\mathcal{L}$ will have vanishing contextual swap regret

###### Proof.

We will prove that $\mathcal{L}$ has vanishing contextual swap regret against
any mechanism $\sigma$. Because this set of mechanisms includes all constant
mechanisms, we now only need to prove this one stronger claim instead of two
claims to satisfy assumption 1. Let $t_{b}$ be the first round when the Agent
defects to begin playing $noreg$. Then, the contextual swap regret of
$\mathcal{L}$ against any sequence $y$ (not necessarily drawn from $y^{*}$)
can be expressed as

$\displaystyle
T\cdot\textrm{SwapReg}(y_{1:T},p_{1:T},r_{1:T})=\mathbb{E}_{\mathcal{L},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T}(U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t})-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}^{\sigma}))\right]\
$
$\displaystyle=\mathbb{E}_{\mathcal{L},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{t_{b}}(U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t})-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]\
+$
$\displaystyle\mathbb{E}_{\mathcal{L},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=t_{b}+1}^{T}(U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t})-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]\
$
$\displaystyle=\mathbb{E}_{\mathcal{L},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{t_{b}}(U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t})-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]\
+$
$\displaystyle\mathbb{E}_{noreg,\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=t_{b}+1}^{T}(U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t})-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]\
$ (By the fact that $\mathcal{L}$ begins playing $noreg$ at $t_{b}+1$)
$\displaystyle\leq
o(T)+\mathbb{E}_{noreg,\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=t_{b}+1}^{T}(U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t})-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]\
$ (By Lemma 26) $\displaystyle\leq o(T)$ (By the fact that $noreg$ has bounded
contextual swap regret)

Thus, $\textrm{SwapReg}(y_{1:T},p_{1:T},r_{1:T})\leq\frac{o(T)}{T}=o(1)$

∎

######  Lemma 21.

As long as $noreg$ has vanishing negative regret, $\mathcal{L}$ will have
vanishing negative regret.

###### Proof.

Let $t_{b}$ be the first round in which the Agent begins playing $noreg$. We
can split up the negative regret of the Agent as follows:

$\displaystyle
T\cdot\textrm{NegReg}(y_{1:T},p_{1:T}^{\sigma},r^{\sigma}_{1:T})=\mathbb{E}_{\mathcal{L},\sigma}\left[\sum_{t=1}^{T}U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})-\max_{h:\mathcal{P}_{0}\times\mathcal{A}\mapsto\mathcal{A}}(h(p_{t}^{\sigma},r_{t}^{\sigma}),p_{t}^{\sigma},y_{t})\right]$
$\displaystyle=\mathbb{E}_{\mathcal{L},\sigma}\left[\sum\right]_{t=1}^{t_{b}}U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})-\max_{h:\mathcal{P}_{0}\times\mathcal{A}\mapsto\mathcal{A}}{\sum_{t=1}^{t_{b}}U(h(p_{t}^{\sigma},r_{t}^{\sigma}),p_{t}^{\sigma},y_{t})}$
$\displaystyle+\mathbb{E}_{noreg,\sigma}\left[\sum\right]_{t=t_{b}+1}^{T}U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})-\max_{h:\mathcal{P}_{0}\times\mathcal{A}\mapsto\mathcal{A}}{\sum_{t=t_{b+1}}^{T}U(h(p_{t}^{\sigma},r_{t}^{\sigma}),p_{t}^{\sigma},y_{t})}$
$\displaystyle\leq\mathbb{E}_{\mathcal{L},\sigma}\left[\sum\right]_{t=1}^{t_{b}}U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})-\max_{h:\mathcal{P}_{0}\times\mathcal{A}\mapsto\mathcal{A}}{\sum_{t=1}^{t_{b}}U(h(p_{t}^{\sigma},r_{t}^{\sigma}),p_{t}^{\sigma},y_{t})}+o(T)$
(By the fact that $noreg$ has vanishing negative regret.) $\displaystyle\leq
o(T)$ ( By Lemma 26.)

Thus, $\textrm{NegReg}\leq\frac{o(T)}{T}=o(1)$.

∎

######  Lemma 22.

$\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})]\leq\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]+o(T)$

###### Proof.

In this proof we use the fact that the distributions $y^{*}|balanced_{all}$
and $y^{*}$ are very close to each other to show that the Principal’s expected
payoff must be similar under both.

$\displaystyle\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})]$
$\displaystyle=\mathbb{P}(balanced_{all})\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]$
$\displaystyle+\mathbb{P}(\neg
balanced_{all})\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|\neg
balanced_{all}]$
$\displaystyle\leq\mathbb{P}(balanced_{all})\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]$
$\displaystyle+T^{-\frac{1}{10}}\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|\neg
balanced_{all}]$ (By Lemma 23)
$\displaystyle\leq\mathbb{P}(balanced_{all})\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]+T^{-\frac{1}{10}}\cdot
T$
$\displaystyle\leq\mathbb{E}_{y^{*},\mathcal{L},\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},(0.5,work),y_{t})|balanced_{all}]+o(T)$

∎

######  Lemma 23.

If $y_{2:T}\sim y^{*}_{2:T}$, with probability at least $1-T^{\frac{1}{10}}$,
$balanced_{all}=true$. Furthermore, $balanced_{all}$ implies that the
difference between the number of $M$ and $H$ states is $o(T)$.

###### Proof.

Let us consider $y^{*}_{2:T}$ to be a sequence of independent, identically
distributed random variables $S$, where the value is $1$ when the state is $M$
and $-1$ otherwise. Then they have mean $0$ and variance $1$. The absolute
value of the difference between the number of $M$ states and the number of $H$
states is now exactly equal to $|S_{T}|=|\sum_{i=1}^{T}y_{i}|$.

This is now a Rademacher random walk. By an application of the nonasymptotic
version of the Law of Iterated Logarithm in Balsubramani [2015], we have that
with probability $\geq 1-T^{-\frac{1}{10}}$, for all $t\leq T$ simultaneously,

$\displaystyle|S_{t}|\leq\sqrt{3t(2log(log(\frac{5}{2}t))+log(2T^{\frac{1}{10}))}}$
$\displaystyle\leq\sqrt{3T(2log(log(\frac{5}{2}T))+log(2T^{\frac{1}{10}))}}=o(T)$

∎

######  Lemma 24.

In expectation over $y^{*}$, the expected payoff of any mechanism $\sigma$
against $noreg$ is at most $o(T)$.

###### Proof.

Let $s_{m,w}$ be the number of rounds in which the state is medium and the
Agent works, and define $s_{h,w}$, $s_{m,s}$, and $s_{h,s}$ accordingly. Let
us assume for contradiction that the Principal receives expected payoff of at
least $c\cdot T$. Then,

$\displaystyle\mathbb{E}_{y_{*},noreg,\sigma}[\sum_{t=1}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]\geq
c\cdot T$
$\displaystyle\Rightarrow\mathbb{E}_{y^{*},noreg,\sigma}[\sum_{t=1}^{T}((2-2p_{t})\cdot\mathbbm{1}[m,w])]\geq
c\cdot T$
$\displaystyle\Rightarrow\mathbb{E}_{y^{*},noreg,\sigma}[2s_{m,w}]-c\cdot
T\geq\mathbb{E}_{y^{*},noreg,\sigma}[\sum_{t=1}^{T}2p_{t}\cdot\mathbbm{1}[m,w])]$

However, by assumption, we also have that

$\displaystyle\mathbb{E}_{y^{*},noreg,\sigma}[\sum_{t=1}^{T}U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]\geq-o(T)$
(By the fact that the Agent could play $shirk$ every round and get $0$)
$\displaystyle\Rightarrow\mathbb{E}_{y^{*},noreg,\sigma}[\sum_{t=1}^{T}(2p_{t}\cdot\mathbbm{1}[m,w])-s_{m,w}-s_{h,w}]\geq-o(T)$
$\displaystyle\Rightarrow\mathbb{E}_{y^{*},noreg,\sigma}[2\cdot s_{m,w}-c\cdot
T-s_{m,w}-s_{h,w}]\geq-o(T)$ (Using the Principal payoff expression)
$\displaystyle\Rightarrow\mathbb{E}_{y^{*},noreg,\sigma}[s_{m,w}-s_{h,w}]\geq
c\cdot T-o(T)>0$ (For sufficiently large $T$)

As $\sigma$ does not take the states of nature as input, we know that
$y_{t}\sim y^{*}$ is independent of $(p_{t},r_{t})$. Furthermore, as $noreg$
does not take the states of nature as input, we know that $a_{t}$, conditioned
on $(p_{t},r_{t})$, is independent of $y_{t}\sim y^{*}$. Putting these
together, we get that $a_{t}$ is independent of $y_{t}$. Therefore,

$\displaystyle\mathbb{E}_{y^{*},noreg,\sigma}[s_{m,w}-s_{h,w}]$
$\displaystyle=\sum_{t=1}^{T}\mathbb{P}_{y^{*},noreg,\sigma}(y_{t}=M,a_{t}=work)-\sum_{t=1}^{T}\mathbb{P}_{y^{*},noreg,\sigma}(y_{t}=H,a_{t}=work)$
$\displaystyle=\sum_{t=1}^{T}\mathbb{P}_{y^{*}_{1:t-1},noreg,\sigma}(a_{t}=work)\cdot\mathbb{P}_{y^{*}_{t}}y_{t}=M)-\sum_{t=1}^{T}\mathbb{P}_{y^{*}_{1:t-1},noreg,\sigma}(a_{t}=work)\cdot\mathbb{P}_{y^{*}_{t}}y_{t}=H)$
(By the independence of $a$ and $y$)
$\displaystyle=\frac{1}{2}\sum_{t=1}^{T}\mathbb{P}_{y^{*}_{1:t-1},noreg,\sigma}(a_{t}=work)-\frac{1}{2}\sum_{t=1}^{T}\mathbb{P}_{y^{*}_{1:t-1},noreg,\sigma}(a_{t}=work)=0$

This derives a contradiction, proving our claim.

∎

######  Lemma 25.

If $y_{1}=M$ then no Principal mechanism can get expected payoff more than
$\frac{T}{4}+o(T)$ payoff against $\mathcal{L}$, in expectation over
$y^{*}_{2:T}$. If $y_{1}=H$ then no Principal mechanism can get expected
payoff more than $\frac{T}{5}+o(T)$ payoff against $\mathcal{L}$, in
expectation over $y^{*}_{2:T}$.

###### Proof.

First, assume $y_{1}=M$. Furthermore, let $t^{\prime}$ be the first round in
which the Principal mechanism $\sigma$ does not play $(0.5,work)$. Then, the
payoff of the Principal is

$\displaystyle\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{t^{\prime}}V(a_{t}^{\sigma},(0.5,work),y_{t})]+\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=t^{\prime}}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle=\mathbb{E}_{y_{2:T}^{*},(a^{*})^{\sigma}}[\sum_{t=1}^{t^{\prime}}V(a_{t}^{\sigma},(0.5,work),y_{t})]+\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=t^{\prime}}^{T}V(noreg^{\sigma},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle=\frac{t^{\prime}}{2}-\frac{t^{\prime}}{4}+\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=t^{\prime}}^{T}V(noreg^{\sigma},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle=\frac{t^{\prime}}{4}+o(T)$ (By Lemma 24)
$\displaystyle\leq\frac{T}{4}+o(T)$

The analysis is similar for $y_{1}=H$. Let $t^{\prime}$ be the first round in
which the Principal mechanism $\sigma$ does not play $(0.6,work)$. Then, the
payoff of the Principal is

$\displaystyle\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=1}^{t^{\prime}}V(a_{t}^{\sigma},(0.6,work),y_{t})]+\mathbb{E}_{y_{2:T}^{*},\mathcal{L},\sigma}[\sum_{t=t^{\prime}}^{T}V(a_{t}^{\sigma},p_{t}^{\sigma},y_{t})]$
$\displaystyle=\mathbb{E}_{y_{2:T}^{*},(b^{*})^{\sigma}}[\sum_{t=1}^{t^{\prime}}V(a_{t}^{\sigma},(0.6,work),y_{t})]+\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=t^{\prime}}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle=\frac{2t^{\prime}}{5}-\frac{t^{\prime}}{5}+\mathbb{E}_{y_{2:T}^{*},noreg,\sigma}[\sum_{t=t^{\prime}}^{T}V(noreg^{{}^{\sigma}},\sigma,p_{t}^{\sigma},y_{t})]$
$\displaystyle=\frac{t^{\prime}}{5}+o(T)$ (By Lemma 24)
$\displaystyle\leq\frac{T}{5}+o(T)$

∎

######  Lemma 26.

For any prefix of play of length $T^{\prime}\leq T$, as long as
$balanced_{all}=true$ and the Principal plays only $0.5,work$ for all
$\sigma$,

$\mathbb{E}_{a^{*},\sigma}[\textrm{SwapReg}(y_{1:T},p_{1:T},r_{1:T})]\leq
o(T)$

and

$\mathbb{E}_{a^{*},\sigma}[\textrm{NegReg}(y_{1:T},p_{1:T}^{\sigma},r^{\sigma}_{1:T})]\leq
o(T)$

Similarly, for any prefix of play of length $T^{\prime}\leq T$, as long as
$balanced_{all}=true$, the Principal plays only $0.6,work$, for all $\sigma$,

$\mathbb{E}_{b^{*},\sigma}[\textrm{SwapReg}(y_{1:T},p_{1:T},r_{1:T})]\leq
o(T)$

and

$\mathbb{E}_{b^{*},\sigma}[\textrm{NegReg}(y_{1:T},p_{1:T}^{\sigma},r^{\sigma}_{1:T})]\leq
o(T)$

###### Proof.

For the first case of $(0.5,work)$ and $a^{*}$, the Agent is always mapping
$M$ to $work$ and $H$ to $shirk$. As $work$ gets payoff $2p-1\geq 0$ under $m$
and $shirk$ gets $0$, while $work$ gets $-1$ under $H$ and $shirk$ gets $0$,
this is the optimal mapping. Therefore the Contextual Swap Regret is $0$. Now
we can upper bound the negative regret:

$\displaystyle\mathbb{E}_{a^{*},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(p_{t}^{\sigma},r_{t}^{\sigma}),p_{t}^{\sigma},y_{t}))-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]$
$\displaystyle=\mathbb{E}_{a^{*},\sigma}\left[\max_{a\in\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(0.5,work),0.5,y_{t}))-U(a_{t}^{\sigma},0.5,y_{t}))\right]$
(By the fact that the Principal is making a fixed (policy, recommendation)
pair across all $t\leq T^{\prime}$)
$\displaystyle=\mathbb{E}_{a^{*},\sigma}\left[\max_{a\in\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(0.5,work),0.5,y_{t}))\right]$
(By definition of $a^{*}$)
$\displaystyle=\max(\mathbb{E}_{a^{*},\sigma}[\sum_{t=1}^{T^{\prime}}U(work,0.5,y_{t})],\mathbb{E}_{a^{*},\sigma}[\sum_{t=1}^{T^{\prime}}U(shirk,0.5,y_{t}))$
$\displaystyle=\max(\mathbb{E}_{a^{*},\sigma}[\frac{1}{2}m_{y,T^{\prime}}-h_{y,T}],0)$
$\displaystyle\leq\max(\mathbb{E}_{a^{*},\sigma}[\frac{1}{2}h_{y,T^{\prime}}+o(T)-h_{y,T}],0)$
(By the fact that $balanced_{t}$ is true over the entire prefix.)
$\displaystyle\leq o(T)$

For the second case of $(0.6,work)$ and $b^{*}$, let us use $m_{y,T^{\prime}}$
to refer to the number of $m$ states in the sequence, and $h_{y,T^{\prime}}$
to refer to the number of $h$ states:

$\displaystyle\mathbb{E}_{b^{*},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(p_{t}^{\sigma},r_{t}^{\sigma},a_{t}^{\sigma}),p_{t}^{\sigma},y_{t}))-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]$
$\displaystyle=\mathbb{E}_{b^{*},\sigma}\left[\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(0.6,work,a_{t}^{\sigma}),0.6,y_{t}))-U(a_{t}^{\sigma},0.6,y_{t}))\right]$
(By the fact that the Principal is making a fixed (policy, recommendation)
pair across all $t\leq T^{\prime}$)
$\displaystyle=\mathbb{E}_{b^{*},\sigma}\left[\max_{h:\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(0.6,work,a_{t}^{\sigma}),0.6,y_{t}))-\frac{1}{5}(m_{y,T^{\prime}}-h_{y,T^{\prime}})\right]$
(By definition of $b^{*}$)
$\displaystyle=\mathbb{E}_{b^{*},\sigma}[\max_{a\in\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(a,0.6,y_{t}))\mathbbm{1}[a_{t}^{\sigma}=work]]$
$\displaystyle+\mathbb{E}_{b^{*},\sigma}[\max_{a\in\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(a,0.6,y_{t}))\mathbbm{1}[a_{t}^{\sigma}=shirk]]-\mathbb{E}_{b^{*},\sigma}[\frac{1}{5}(m_{y,T^{\prime}}-h_{y,T^{\prime}})]$
$\displaystyle=\max(\mathbb{E}_{b^{*},\sigma}[\sum_{t=1}^{T^{\prime}}U(work,0.6,H))\mathbbm{1}[a_{t}^{\sigma}=shirk]],0)-\frac{1}{5}(m_{y,T^{\prime}}-h_{y,T^{\prime}})$
(By the fact that $b^{*}$ only shirks when $y=H$, and that shirking always
guarantees payoff $0$.)
$\displaystyle=\max(m_{y},T^{\prime}-h_{y,T^{\prime}},0)-\frac{1}{5}(m_{y,T^{\prime}}-h_{y,T^{\prime}})$
(By the distribution of the states conditioned on $b^{*}$ playing $work$)
$\displaystyle\leq o(T)$ (By the fact that $balanced_{t}$ is true over the
entire prefix.)

Thus, in the second case the Contextual Swap Regret is upper bounded. Finally,
we need that the Negative Regret is upper bounded:

$\displaystyle\mathbb{E}_{b^{*},\sigma}\left[\max_{h:\mathcal{P}\times\mathcal{A}\mapsto\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(p_{t}^{\sigma},r_{t}^{\sigma}),p_{t}^{\sigma},y_{t}))-U(a_{t}^{\sigma},p_{t}^{\sigma},y_{t}))\right]$
$\displaystyle=\mathbb{E}_{b^{*},\sigma}\left[\max_{a\in\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(0.6,work),0.6,y_{t}))-U(a_{t}^{\sigma},0.6,y_{t}))\right]$
(By the fact that the Principal is making a fixed (policy, recommendation)
pair across all $t\leq T^{\prime}$)
$\displaystyle=\mathbb{E}_{a^{*},\sigma}\left[\max_{a\in\mathcal{A}}\sum_{t=1}^{T^{\prime}}U(h(0.6,work),0.6,y_{t}))-\frac{1}{5}(m_{y,T^{\prime}}-h_{y,T^{\prime}})\right]$
(By definition of $b^{*}$)
$\displaystyle=\max(\mathbb{E}_{b^{*},\sigma}[\sum_{t=1}^{T^{\prime}}U(work,0.6,y_{t})],\mathbb{E}_{a^{*},\sigma}[\sum_{t=1}^{T^{\prime}}U(shirk,0.6,y_{t}))-\mathbb{E}_{a^{*},\sigma}[(m_{y,T^{\prime}}-h_{y,T^{\prime}})]$
$\displaystyle=\max(\mathbb{E}_{b^{*},\sigma}[\frac{1}{2}m_{y,T^{\prime}}-h_{y,T}],0)-\mathbb{E}_{b^{*},\sigma}[(m_{y,T^{\prime}}-h_{y,T^{\prime}})]$
$\displaystyle\leq o(T)$ (By the fact that $balanced_{t}$ is true over the
entire prefix.)

∎