≤2
13×
4×
18

\(\displaystyle \min_{\pi}\ \mathcal R(\pi;\alpha)=\mathbb E\Big[\underbrace{\sum_{t=1}^{\tau} c_{j_t}}_{\text{query bill}}+ g\Big(\underbrace{\sum_{t=1}^{\tau} T_{j_t,t}}_{\text{total waiting time}}\Big)\Big]\)\(\displaystyle g(x)=c\,x^{\rho},\ \ \rho\ge 1\)
\(\displaystyle \begin{aligned}\min_{\pi}\ \mathcal R(\pi;\alpha)=\mathbb E\Big[&\sum_{t=1}^{\tau} c_{j_t}\\&+ g\Big(\sum_{t=1}^{\tau} T_{j_t,t}\Big)\Big]\end{aligned}\)\(\displaystyle g(x)=c\,x^{\rho},\ \ \rho\ge 1\)

\(\displaystyle I_{j,A}=\mathrm{KL}\big(P_{j,A}\,\|\,P_{j,B}\big)\)\(\displaystyle I_{j,B}=\mathrm{KL}\big(P_{j,B}\,\|\,P_{j,A}\big)\)\(\displaystyle \kappa_{j,\theta}=\frac{c_j}{I_{j,\theta}}\)\(\displaystyle \eta_{j,\theta}=\frac{\mu_j}{I_{j,\theta}}\)
\(\gamma_{j,A},\ \gamma_{j,B}\in(\tfrac12,1)\)
\(c_j\)
\(\mu_j=\mathbb E[T_{j,t}]\)
\(\xi_A,\ \alpha,\ g(x)=c\,x^{\rho}\)

\(\displaystyle \mathbb P_A\big(N_j(\tau)\ge 1\ \text{ for all } j\in[M_\alpha]\big)\ \ge\ 1-M_\alpha\,\frac{\alpha}{1-\alpha}\)\(\displaystyle M_\alpha=\Big\lfloor\sqrt{\log\tfrac{1-\alpha}{\alpha}}\Big\rfloor\ \to\ \infty\)
\(\displaystyle \begin{aligned}&\mathbb P_A\big(N_j(\tau)\ge 1\ \ \forall j\in[M_\alpha]\big)\\&\qquad\ge\ 1-M_\alpha\,\frac{\alpha}{1-\alpha}\end{aligned}\)\(\displaystyle M_\alpha=\Big\lfloor\sqrt{\log\tfrac{1-\alpha}{\alpha}}\Big\rfloor\ \to\ \infty\)

\(\displaystyle j_\theta^\star\in\arg\min_{j\in[M]}\Big\{S_\theta(\alpha)\,\kappa_{j,\theta}+g\big(S_\theta(\alpha)\,\eta_{j,\theta}\big)\Big\}\)\(\displaystyle S_\theta(\alpha)=\log\tfrac{1}{\alpha}+O(1),\ \ \theta\in\{A,B\}\)
\(\displaystyle \begin{aligned}j_\theta^\star\in\arg\min_{j\in[M]}\Big\{&S_\theta(\alpha)\,\kappa_{j,\theta}\\&+g\big(S_\theta(\alpha)\,\eta_{j,\theta}\big)\Big\}\end{aligned}\)\(\displaystyle S_\theta(\alpha)=\log\tfrac{1}{\alpha}+O(1),\ \ \theta\in\{A,B\}\)
\(\delta+L_{t-1}\ge 0\)

\(L_t\ge A_\alpha\ \ \text{or}\ \ L_t\le -B_\alpha\)
\(\delta+L_{t-1}< 0\)

\(\displaystyle L_t=\sum_{s=1}^{t}\ell_{j_s}(Y_s)\)\(\displaystyle A_\alpha=\log\frac{1-\alpha}{\alpha}-\delta\)\(\displaystyle B_\alpha=\log\frac{1-\alpha}{\alpha}+\delta\)\(\displaystyle \delta=\log\frac{\xi_A}{\xi_B}\)

01

02

03

04

\(\displaystyle \Psi_\alpha=\min_{\mathbf n_A,\,\mathbf n_B\ge 0}\ \sum_{\theta\in\{A,B\}}\xi_\theta\Big[\sum_{j=1}^{M}c_j\,n_{j,\theta}+g\Big(\sum_{j=1}^{M}\mu_j\,n_{j,\theta}\Big)\Big]\)\(\displaystyle \text{s.t.}\ \ \sum_{j=1}^{M}I_{j,\theta}\,n_{j,\theta}=S_\theta(\alpha),\ \ \theta\in\{A,B\}\)
\(\displaystyle \Psi_\alpha=\min_{\mathbf n_A,\,\mathbf n_B\ge 0}\ F(\mathbf n_A,\mathbf n_B)\)\(\displaystyle \begin{aligned}F=\sum_{\theta}\xi_\theta\Big[&\sum_{j}c_j\,n_{j,\theta}\\&+g\Big(\sum_{j}\mu_j\,n_{j,\theta}\Big)\Big]\end{aligned}\)\(\displaystyle \text{s.t.}\ \ \sum_{j}I_{j,\theta}\,n_{j,\theta}=S_\theta(\alpha),\ \ \theta\in\{A,B\}\)

LLM\(I_{j,A}\)\(I_{j,B}\)\(c_j\)\(\mu_j\)
1511010
2151010
\(\displaystyle \frac{\Psi^{(1)}_\alpha}{\Psi_\alpha}\ \xrightarrow[\ \alpha\to 0\ ]{}\ \frac{1+5^{\rho}}{2}\)\(\displaystyle =\begin{cases}3, & \rho=1,\\[2pt] 13, & \rho=2.\end{cases}\)

\(\displaystyle \gamma_{j,A}=\tfrac12+a_j\epsilon,\quad \gamma_{j,B}=\tfrac12+b_j\epsilon\)\(\displaystyle \lim_{\alpha\to 0}\ \lim_{\epsilon\to 0}\ \frac{\mathcal R^{\mathrm{st},*}(\alpha)}{\mathcal R^{*}(\alpha)}=4\)

\(\displaystyle \operatorname{Gap}=\frac{\widehat{\mathcal R}_{\mathsf{2LLM}}-\mathcal R_{\mathrm{Bellman}}}{\mathcal R_{\mathrm{Bellman}}}\times 100\%\)
\(\alpha=10^{-1}\)\(\alpha=10^{-3}\)\(10^{-10}\le\alpha\le 10^{-7}\)
3–34%1–7%
20–52%4–13%

\(\displaystyle \mathcal R(\pi;\alpha)=\Psi_\alpha+O\big((\log\tfrac1\alpha)^{\rho-1}\big)\)\(\displaystyle \Psi_\alpha=\Theta\big((\log\tfrac1\alpha)^{\rho}\big)\)

\(\displaystyle \inf_{\pi\in\Pi(\alpha)}\mathcal R(\pi;\alpha)\ \ge\ \Psi_\alpha+K\,(\log\tfrac1\alpha)^{\rho-1}\)\(\displaystyle (\rho>1)\)