# Some comments about CRC selection for the 5G NR specification

Tsonka Baicheva, Peter Kazakov, and Miroslav Dimitrov T. Baicheva, P. Kazakov
and M. Dimitrov were with the Institute of Mathematics and Informatics,
Bulgarian Academy of Sciences, Sofia, Bulgaria. P. Kazakov was also with
AtScale, Sofia, Bulgaria.

###### Abstract

In this work the undetected error probability performance of the proposed in
the technical specification of 5G new radio cyclic redundancy-check codes
taking into consideration that they have to work for fixed interval of lengths
are investigated. Codes of 6, 11 and 16 check bits with better error detection
performance than the proposed in the specification ones are suggested. For 24
check bits the 3 best CRC codes are presented, but no only one best for the
whole interval of lengths code was found.

###### Index Terms:

CRC codes, undetected error probability, Binary Symmetric channel, 5G NR
specification.

##  I Introduction

According to the technical specification of the 5G new radio (5G NR) [1], data
and control streams from/to MAC layer are encoded/decoded to offer transport
and control services over the radio transmission link. Channel coding scheme
is a combination of error detection, error correction, rate matching,
interleaving and transport channel or control information mapping
onto/splitting from physical channels. For error detection cyclic redundancy-
check (CRC) codes or combination of LDPC and CRC codes are used. Six CRC codes
are proposed in the specification and they are specified to work for different
payloads (information stream lengths) $A$. The proposed CRC codes are
summarized in Table I.

TABLE I: CRC codes used in 5G NR Label | Polynomial
---|---
CRC6 | $x^{6}+x^{5}+1$
CRC11 | $x^{11}+x^{10}+x^{9}+x^{5}+1$
CRC16 | $x^{16}+x^{12}+x^{5}+1$
CRC24A |  $x^{24}+x^{23}+x^{18}+x^{17}++x^{14}+$ $+x^{11}+x^{10}+x^{7}+x^{6}+x^{5}+x^{4}+x^{3}+x+1$
CRC24B | $x^{24}+x^{23}+x^{6}+x^{5}+x+1$
CRC24C |  $x^{24}+x^{23}+x^{21}+x^{20}+x^{17}+x^{15}+$ $+x^{13}+x^{12}+x^{8}+x^{4}+x^{2}+x+1$

For the uplink and downlink shared channels, CRC16 should be used if the
transport block size $A$ is $1\leq A\leq 3824$, while for $3824\leq A\leq
8424$, CRC24A is proposed. LDPC codes are combined with CRC24B for block sizes
$A\leq 8424$. For the downlink broadcast channel, where $A\leq 8424$, CRC24C
is suggested. Error detection in the uplink control channel for $12\leq A\leq
19$ should be done by CRC6, for $20\leq A\leq 1706$ by CRC11 while in the
downlink control channel, where $A\leq 140$, CRC24C should be used.

In this letter we investigate the error detection performance of the
aforementioned CRC codes. The work is organized as follows. First we briefly
recall the basic techniques of measuring the error detection performance of a
given CRC code. Then we suggest different collection of six CRC codes which
outperform, in terms of undetected error probability, those proposed in 5G NR.
We compare the two collections of codes by applying both the optimization
criterion and the additionally speed up investigation method suggested in our
previous work [2]. Although that in [2] we obtain best CRC codes for 11 and 16
check bits we did the investigation again as in the 5G NR specification CRC
codes have to work in a fixed range of lengths which do not coincide with
those in [2]. As the results show, the best CRC code with 11 check bits is
different than the obtained in [2].

##  II Basic facts about CRC codes

CRC codes are first introduced by Peterson and Brown in [3]. Very good sources
describing the theoretical foundations and properties of CRC codes are
Peterson and Weldon’s [4] and Wicker’s [5] books. In this section, the main
results regarding the structure and error detection properties of CRC codes
are summarized and introduced.

CRC codes are full length or shortened linear binary cyclic codes. Each
codeword of a CRC code has $n=k+p$ binary digits and is obtained by adding in
a definite way a block of $p$ parity bits to an information block of $k$
binary digits

Any CRC code may be represented as a set of polynomials where instead of the
information block of $k$ binary digits, the polynomial

$i(x)=i_{0}+i_{1}x+\dots+i_{k-1}x^{k-1},$

and instead of the block of $p$ parity bits the polynomial

$r(x)=r_{0}+r_{1}x+\dots+r_{p-1}x^{p-1}$

are used. Then in each CRC code with $p$ check bits there exists a polynomial
of degree $p$ called the generator polynomial $g(x)$ of the code. The leading
and zero coefficients of $g(x)$ are nonzero.

Each codeword $c(x)$ of the CRC code is obtained by computing $r(x)$ from
$i(x)$ in the following way

$r(x)\equiv(x^{p}.i(x))~{}mod~{}g(x).$

According to this encoding the following equations holds

$c(x)=x^{p}i(x)+r(x)=q(x)g(x)+r(x)+r(x)=q(x)g(x)$

for some polynomial $q(x)$. Thus, the recipient could easily decides if a
given word is a codeword or not by checking its divisibility to $g(x)$.

The polynomial $g(x)$ divides $x^{n_{c}}+1$, where

$n_{c}=\min\\{m|x^{m}\equiv 1~{}mod~{}g(x)\\}$

is called order of the polynomial $g(x)$. The binary cyclic code $D$ generated
by the polynomial $g(x)$ of degree $p$ is a $[n_{c},n_{c}-p]$ code. Any
$[n,n-p]$ subcode $C$ of $D$ obtained by shortening $D$ in $n_{c}-n$ positions
is a CRC code. The maximum length at which any CRC code can be used is equal
to the order of the generator polynomial $n_{c}$. For longer lengths the code
is no more CRC code. More precisely, it becomes a repetition code with minimum
distance 2. This means that it can detect only 1 error and does not posses the
ability to detect burst errors.

Given their excellent error detection capabilities, CRC codes are widely
exploited by manifold applications.

In summary, CRC codes of length $n$ and minimum distance $d$, generated by the
polynomial $g(x)$ of degree $p$, could detect:

  * •

all combinations of up to $d-1$ errors;

  * •

all error bursts (any pattern of errors for which the number of symbols
between the first and last errors, including the errors, is $b$) of length
$b\leq p$;

  * •

a fraction of all bursts of length $b=p+1$ (the fraction equals
$1-2^{-(p-1)}$);

Let us consider communication through a Binary Symmetric Channel (BSC). BSC is
a discrete memoryless channel with binary input and output and crossover
probability $\varepsilon$, where $0\leq\varepsilon\leq 1/2$. During the
transmission, the send codeword $c(x)$ may be changed by the channel noise and
the receiver to get another polynomial $c^{\prime}(x)=c(x)+e(x)$. The nonzero
coefficients of the error polynomial $e(x)$ correspond to the positions which
are changed by the noise. At the receiving end $c^{\prime}(x)$ is divided by
the generator polynomial $g(x)$ and an error is detected if the reminder of
the division is not zero. However, it may happened that the channel noise
changes $c(x)$ in such a way that $c^{\prime}(x)$ is another codeword. In this
case we have an undetected error. As the CRC codes are linear, we will have
undetected error if and only if $e(x)$ is a codeword.

Let us denote by $A_{i}$ and $B_{i}$ the number of codewords of weight $i$ in
the CRC code and in its dual. Then the error detection performance of a CRC
code of length $n$ with $p$ check symbols is measured by the probability
$P_{ue}$ of undetectable errors [6]:

$P_{ue}=\sum_{i=1}^{n}A_{i}\varepsilon^{i}(1-\varepsilon)^{n-i}=2^{-p}[1+\sum_{i=1}^{n}B_{i}(1-2\varepsilon)^{i}]-(1-\varepsilon)^{n}.$

Therefore, the best choose of a CRC code is the one having the smallest value
of $P_{ue}$. As $P_{ue}$ depends on the crossover probability $\varepsilon$
and the length $n$ of the CRC code we may have different best codes for
different $\varepsilon$ and $n$.

##  III Complexity of the determination of $P_{ue}$ of a code

Let us denote by $d$ the minimum distance of an $[n,n-p]$ CRC code generated
by the polynomial $g(x)$ and shortened in $n_{c}-n$ positions. It has been
proven in [7] that determination of the set $\\{A_{i}\\}_{i=1}^{n}$ (or
$\\{B_{i}\\}_{i=1}^{n}$ respectively) for a $[n,n-p]$ code is a
computationally hard problem. Thus the comparison of the values of $P_{ue}$
for two particular codes is also computationally hard problem.

In order to reduce the computational complexity of the problem we could
compare $P_{ue}^{\prime}=A_{d}\varepsilon^{d}(1-\varepsilon)^{n-d}$, i.e. to
calculate only the first nonzero addend of the sum for $P_{ue}$, as it is the
most significant one (especially for small values of $\varepsilon$). By using
this approach, only the number of codewords with minimum weight is needed.

Comparing $P_{ue}^{\prime}$ performances of two codes we can obtain rather
precise result as it can be seen in Figure 1. The actual difference between
the the undetected error probabilities of the compared codes is several times
bigger than that obtained by comparing only its $P_{ue}^{\prime}$s. This
approach has been used by Kazakov in [8] to determine optimal with respect to
$A_{d}$ CRC codes with 16 check bits.

Figure 1: Comparison of $P_{ue}$ and $P_{ue}^{\prime}$ of two CRC codes

##  IV Search for optimal CRC codes with $p$ check symbols

The proposed in the 5G NR specification CRC codes will be used to protect
information packages of different lengths. That is way our aim is to chose a
CRC code having the best performance not only for a particular length but for
the whole range of lengths at which the code is supposed to work.

We denote by $d(C_{g,n})$ the minimum distance of a CRC code of length $n$,
with generator polynomial $g(x)$, supposed to work in an interval of lengths
between $L$ and $M$. Since the CRC code can be used at any length of the
interval $[L\dots M]$ its cumulative performance in the whole interval should
be investigated. Thus, for any polynomial $g(x)$ of degree $p$, which could be
generator polynomial of a CRC code of length $n\in[L\dots M]]$ we calculate

$S_{d}=\sum_{n=L}^{M}d(C_{g,n}).$

The CRC code with a maximum value of $S_{d}$ is the optimal one.

In order to obtain $d(C_{g,n})$, we have to generate all $2^{n-p}$ codewords
of the CRC code and to determine their weights as the minimum distance of a
binary linear code is equal to the minimum weight of its codewords. Given some
fixed CRC code, to calculate $S_{d}$ we have to repeat this procedure $M-L+1$
times. However, instead to generate the $2^{n-p}$ codewords of the CRC code
$C$, we can generate only the $2^{p}$ codewords of its dual code $C^{\prime}$
and compute the minimum distance of $C$ in linear time via MacWilliams’
identities [9].

To calculate the values of $S_{d}$ for all CRC codes with $p=6,11,16,24$
parity bits we apply the same divide and conquer technique suggested in [2].
To speed up the algorithm additionally, we use a new early rejection criteria
by requiring minimum distance 6 for large code lengths and apply some improved
programming techniques. Then for each $p=6,11,16,24$ we determine the CRC code
having maximum $S_{d}$. If we obtain more than one code of maximum $S_{d}$, we
consider those having the smallest sum of the numbers of codewords with
minimum weight, i.e. minimum $S_{A_{d}}=\sum_{n=L}^{M}A_{d}$.

##  V Results

In Table II we summarize the range of code lengths at which the proposed in 5G
NR technical specification CRC codes are defined to work.

TABLE II: Lengths at which CRC codes from 5G NR specification are applicable. CRC code | $L$ | $M$
---|---|---
CRC6 | 18 | 25
CRC11 | 31 | 1717
CRC16 | 17 | 3840
CRC24A | 3848 | 8448
CRC24B | 25 | 8448
CRC24C | 25 | 164 or 8448

For CRC codes with $p=6,11,16$ or 24 parity bits, we determine the best ones,
by following the strategy described throughout the previous section. We
consider only CRC codes of lengths in the interval $[L\dots M]$ according to
Table II. Given a fixed number of parity bits $p$, we have to consider
$2^{p-1}$ polynomials - possible generators of a CRC code. However, we could
reduce this number by omitting the reciprocal ones, since they generate
equivalent codes or codes with orders smaller than $M$.

###  V-A CRC codes of $p=6$

All polynomials of degree $6$ that could generate CRC codes are $2^{5}=32$.
After excluding the reciprocal they remain 19. Only 8 polynomials out of these
19 have orders greater than 25 (for $p=6$, $M=25$) and we consider only them.
In Table III we summarize the obtained results. The generator polynomials of
the CRC codes are presented in a hexadecimal notation, i.e.
$x^{6}+x^{5}+x^{4}+x+1$ is $73$, while their respective reciprocal polynomials
are given in the brackets. The weight spectra of the first two codes are not
calculated, because they have smaller $S_{d}$ than the others. In the table
are also provided the order $n_{c}$ of the polynomial, the minimum distances
of the CRC codes and the interval of lengths for which the code has the
corresponding minimum distance.

TABLE III: Results for CRC codes with 6 check symbols. $g(x)$ | $n_{c}$ | $S_{d}$ | $S_{A_{d}}$ | minimum distances
---|---|---|---|---
73 (67) | 63 | 24 | - | -
6d (5b) | 63 | 24 | - | -
61 (43) CRC6 | 63 | 24 | 173 | 3,18…25
47 (71) | 31 | 32 | 1959 | 4,18…25
59 (4d) optimal | 31 | 32 | 1956 | 4,18…25
7b (6f) | 31 | 32 | 1966 | 4,18…25
7d (5f) | 30 | 32 | 1962 | 4,18…25
4b (96) | 28 | 32 | 1959 | 4,18…25

According to our optimization criterion, the CRC code generated by the
polynomial 59 is optimal. However, all five codes with a maximum value of
$S_{d}$ have very close values of $S_{A_{d}}$. Thus the differences of their
$P_{ue}$ values are negligible and any of them could be a good choice. The
code with generator polynomial 47 is also suggested by Philip Koopman in its
”Best CRC polynomials” web cite [10] as the best general-purpose polynomial
generating CRC code with 6 check bits (as 0x23 with HD=4) and having maximum
minimum distance profile. The CRC code with generator polynomial 61 is the
proposed in 5G NR CRC6 code and any of the five codes with $S_{d}=32$ will
have much better performance than them. In Figure 2 we present comparison
between the $P_{ue}^{\prime}$ of the CRC codes with generator polynomials 61
and 59 for $\varepsilon=10^{-12}$ and all lengths $n$ at which the code is
supposed to be used. The suggested by us optimal code is at least 100% better
than CRC6 at all lengths. This result is not surprising as CRC6 has minimum
distance 3 for all lengths from 18 to 25 while the optimal CRC code has
minimum distance 4.

Figure 2: Comparison of $P_{ue}^{\prime}$ of CRC6 and the optimal CRC codes.

###  V-B CRC codes of $p=11$

There are $2^{10}=1024$ possible choices for generator polynomials of CRC
codes of degree $11$. After excluding the reciprocal and those of order
smaller than 1717, we obtain that the CRC code generated by the polynomial e0f
has maximum $S_{d}$. In Table IV we present the results regarding the CRC
codes generated by the e0f polynomial and the proposed in 5G NR one generated
by the polynomial e21 (CRC11). The proposed in [2] 93f polynomial is not
optimal in this investigation as it has maximum $S_{d}$ for lengths between 12
and 512 but not for the longer interval of lengths between between 31 and
1717. The CRC code generated by the e0f polynomial possesses significantly
better performance than CRC11 in the interval of lengths $55\dots 149$ where
it has minimum distance 4 while CRC11 has 3. For example, for
$\varepsilon=10^{-12}$ at length 130 the optimal code is 100% better than
CRC11, at length 300 it is 50% better, while at length 1000 it is 0,3% better.

TABLE IV: Results for CRC codes with 11 check symbols. $g(x)$ | $n_{c}$ | $S_{d}$ | minimum distances
---|---|---|---
e0f (f07) | 1953 | 5180 | 3,150…1717;4,31…149
e21 (847) CRC11 | 2047 | 5085 | 3,55…1717;4,31…53

###  V-C CRC codes of $p=16$

For CRC codes with 16 check bits, the maximum $S_{d}$ for lengths up to 3840
has the polynomial 1a2eb. In Table V the values of $S_{d}$ for the polynomials
1a2eb and 11021 (CRC16) are given. The polynomial 1a2eb is suggested by Funk
[11] (321353 in his notation) as the polynomial which generates CRC codes with
the best undetected error probability performance for the whole range of
lengths (17..32767) it can be used. This polynomial is also suggested by
Koopman [10] in the maintained by him website as well as in our previous work
[2]. Its performance will be much more better for lengths up to 109. For
example, for $\varepsilon=10^{-12}$ at lengths 23 and 100 the optimal code is
100% better than CRC16, at length 620 it is 2% better and at length 2500 it is
0,8% better.

TABLE V: Results for CRC codes with 16 check symbols. $g(x)$ | $n_{c}$ | $S_{d}$ | minimum distances
---|---|---|---
1a2eb (1ae8b) | 32767 | 15508 | 4,110…3840;6,28…109;
|  |  | 8,19…27;10,17…18
11021 (10811) CRC16 | 32767 | 15296 | 4,17…3840

###  V-D CRC codes of $p=24$

Since all of the three suggested CRC codes with 24 check bits should work for
lengths up to 8448 we put $M=8448$. The results about the first three best
polynomials obtained by us, together with those three suggested in 5G NR, are
given in Table VI. In Table VII the minimum distances of the codes from Table
VI are given. The suggested CRC24A and CRC24B polynomials are standardized
ones known as CRC-24-Radix-64 and WCDMA 24 correspondingly. The three
suggested in 5G NR CRC24 polynomials are good in general and can be found on
Koopman’s website [10]. In our investigation we take into consideration the
interval of lengths (i.e. $[L\dots M]$) for which the codes will be used and
find the best for this particular interval of lengths codes. Thus the three
codes suggested by us have the best values of $S_{d}$ for the interval
$[25\dots 8448]$. In contrast with the CRC codes of 6, 11 and 16 bits where
there is unique code which has the best performance in the whole interval
$[L\dots M]$ for codes with 24 bits different codes are optimal for different
lengths and we present the three best ones according to our optimization
criterion. For example, at length 920 the three optimal codes are between 94%
and 100% better than the three suggested in 5G NR CRC24 codes. For the code
lengths from the interval $[3848\dots 8448]$ CRC24A, CRC24B and the suggested
by us three codes have minimum distance 4 (see Table VII) for the whole
interval and their performance is very close. For example, the optimal codes
are only 2% better than CRC24A at length 4000 and they perform slightly worse
for lengths above 7060 where CRCA has smaller number of codewords of minimum
weight. As the suggested by us three codes have better values of $S_{d}$ they
will perform better in general (i.e. when they are used at different lengths)
ant their slightly worst performance at lengths close to the end of the
interval $[3848\dots 8448]$ will be compensated by their much better
performance at shorter lengths.

The suggested in [2] 11175b7 polynomial generates CRC codes with best value of
$S_{d}$ for lengths between 25 and 512. It has order 1195740 and could be used
in the interval $[25\dots 8448]$ but would has worse performance than the
suggested in this work three CRC codes because it has minimum distance 6 only
to length 586. This example illustrates once again the necessity to take into
consideration the particular conditions (length, bit error rate) at which the
code will be used in order to obtain the best one.

We do not consider the interval $[25\dots 164]$ since the same code will also
be used for the interval $[25\dots 8448]$. We only note for a completeness
that for the interval $[25\dots 164]$ CRC24C has better performance with
$S_{d}=924$ than the suggested by us codes where the best $S_{d}=802$ is
achieved by 118b983. Thus CRC24C is a good choice if it is used only for
lengths between 25 and 164.

TABLE VI: Results for CRC codes with 24 check symbols. $g(x)$ | $n_{c}$ | $S_{d}$
---|---|---
118b933 (1993a31) | 139230 | 35584
125ae5d (174eb49) | 6241542 | 35564
10f6f6d (16dede1) | 294903 | 35548
1864cfb (1be64c3) CRC24A | 8388607 | 34816
1800063 (18c0003) CRC24B | 8388607 | 33704
1b2b117 (1d11a9b) CRC24C | 28062 | 31109
TABLE VII: Minimum distances for CRC codes with 24 check symbols. $g(x)$ | minimum distances
---|---
118b933 (1993a31) | 4,916…8448; 6,60…915;8,39…59;
| 10,29…38;12,25…28
125ae5d (174eb49) | 4,896…8448; 6,64…895;8,43…63;
| 10,28…42;14,25…27
10f6f6d (16dede1) | 4,881…8448; 6,74…880;8,42…73;
| 10,27…41;14,25…26
1864cfb (1be64c3) CRC24A | 4,542…8448; 6,55…541;8,34…54;
| 10,28…33;12,26…27;14,25
1800063 (18c0003) CRC24B | 4,29…8448; 6,25…28
1b2b117 (1d11a9b) CRC24C | 3,5135…8448; 4,504…5134;5,503…182;
| 6,52…181;7,43…51;9,32…42;13,25…31

##  VI Conclusion

The error control performance of CRC codes with 6, 11, 16 and 24 check bits
for the particular lengths at which the proposed in the technical
specification of 5G new radio CRC codes are supposed to be used is
investigated. For each number of check bits optimal codes are suggested and
their performance is compared to the performance of the aforementioned
proposed codes.

## Acknowledgment

The work of the first and the third authors has been partially supported by
the Bulgarian National Science Fund under contract number 12/8 15.12.2017. The
work of the second author has been partially supported by the National
Scientific Program ”Information and Communication Technologies for a Single
Digital Market in Science, Education and Security” of the Bulgarian Ministry
of Education and Science.

## References

  * [1] “5g nr technical specification,” https://www.etsi.org/deliver/etsi_ts/138200_138299/138212/15.03.00_60/ts_138212v150300p.pdf, accessed: 2021-02-03.
  * [2] T. Baicheva and P. Kazakov, “Crc selection for decoding of crc-polar concatenated code,” _ACM ICPS_ , vol. 9-th Balkan Conference in Informatics, pp. 1–5, 2019.
  * [3] W. W. Peterson and D. T. Brown, “Cyclic codes for error detection,” _Proceedings of the IRE_ , vol. 49, no. 1, pp. 228–235, 1961.
  * [4] W. W. Peterson, W. Peterson, E. Weldon, and E. Weldon, _Error-correcting codes_. MIT press, 1972.
  * [5] S. B. Wicker, _Error control systems for digital communication and storage_. Prentice hall Englewood Cliffs, 1995, vol. 1.
  * [6] J. Wolf, A. Michelson, and A. Levesque, “On the probability of undetected error for linear block codes,” _IEEE Transactions on communications_ , vol. 30, no. 2, pp. 317–325, 1982.
  * [7] A. Vardy, “The intractability of computing the minimum distance of a code,” _IEEE Transactions on Information Theory_ , vol. 43, no. 6, pp. 1757–1766, 1997.
  * [8] P. Kazakov, “Fast calculation on the number of minimum weight words of crc codes,” _IEEE Transactions on Information Theory_ , vol. 49, pp. 1190–1195, 2001.
  * [9] J. MacWilliams, “A theorem on the distribution of weights in a systematic code,” _Bell System Technical Journal_ , vol. 42, no. 1, pp. 79–94, 1963\.
  * [10] “Best crc codes,” https://users.ece.cmu.edu//\~koopman/crc/, accessed: 2020-06-16.
  * [11] G. Funk, “Determination of best shortened linear codes,” _IEEE transactions on communications_ , vol. 44, no. 1, pp. 1–6, 1996.


# Non-stationary Dynamic Pricing via Actor-Critic Information-Directed Pricing

Po-Yi Liu
Department of Statistics
National Chengchi University
Taipei, Taiwan
<EMAIL_ADDRESS>
Chi-Hua Wang
Department of Statistics
University of California
Los Angeles, CA, USA
<EMAIL_ADDRESS>
Henghsiu Tsai
Institute of Statistical Science
Academia Sinica
Taipei, Taiwan
<EMAIL_ADDRESS>

###### Abstract

This paper presents a novel non-stationary dynamic pricing algorithm design,
where pricing agents face incomplete demand information and market environment
shifts. The agents run price experiments to learn about each product’s demand
curve and the profit-maximizing price, while being aware of market environment
shifts to avoid high opportunity costs from offering sub-optimal prices. The
proposed ACIDP extends information-directed sampling (IDS) algorithms from
statistical machine learning to include microeconomic choice theory, with a
novel pricing strategy auditing procedure to escape sub-optimal pricing after
market environment shift. The proposed ACIDP outperforms competing bandit
algorithms including Upper Confidence Bound (UCB) and Thompson sampling (TS)
in a series of market environment shifts.

##  1 Introduction

We consider a non-stationary dynamic pricing problem, a setting in which
pricing agents run pricing experiments to learn incomplete demand information
to cover profit-maximizing price (dynamic pricing) while being mindful of high
opportunity costs from offering sub-optimal price due to market environment
shift (non-stationary). Such a setting arises naturally in industrial practice
but remains unanswered in the literature, preventing practitioners from
deploying state-of-the-art online decision-making methodology effectively in
modern online service industries.

Learning incomplete demand information from pricing experiments is in emerging
demand from industrial practice due to the opportunity cost accompanied with
sub-optimal price and inefficient exploration.[Misra et al., 2019].
Unfortunately, even when algorithms find optimal prices successfully, the
offered price degrades to sub-optimal once the market environment shifts.
Therefore, it is desirable to systematically detect the environmental changes,
abolish the running pricing strategy that appears to be unpromising, and turn
to collect the latest market information. Regrettably, though optimality had
been well studied in the existing designs of multi-armed bandit (MAB)
algorithms including Upper Confidence Bounds (UCB) [Lai et al., 1985, Auer et
al., 2002, Garivier and Cappé, 2011, Maillard et al., 2011, Kaufmann et al.,
2012], Thompson Sampling (TS) [Thompson, 1933, Granmo, 2010, Scott, 2010,
Chapelle and Li, 2011, May and Leslie, 2011, Russo et al., 2018, Russo and Van
Roy, 2016] and Information Directed Sampling (IDS) [Russo and Van Roy, 2018,
Kirschner et al., 2020, 2021], they failed to transfer their learned decision
mechanism into the shifted market environment. In modern dynamic pricing
practice, deployment of MAB methodology turns out to be impeded by such
transfer inability. Resolving transfer inability is crucial to the advancement
of practical dynamic pricing policy.

Online hypothesis testing is the key statistical instrument to assess and
monitor the credibility of learned demand information. These test statistics
measure the discrepancy between the learned and current market environment
model, suggesting possible pricing optimality disruption. The fundamental
rationality of such alarm is to utilize the unlikely occurrence of large
deviations given the null hypothesis, the non-existence of environmental
changes. Yet, these tools are far from both dynamic pricing and bandit
literature, encouraging our investigation of the non-stationary dynamic
pricing problems.

Solving this fundamental problem based on existing knowledge of MAB pricing
[Misra et al., 2019] requires overcoming three major challenges:

(a) Market environment shift. Depart from optimality in the stationary
environment of existing bandit algorithm design, our approach should allow
environment shift alarm and quick reaction to change sub-optimal price to the
new optimal price to reduce regrettable opportunity cost.

(b) Indirect customer feedback. Depart from independent assumption between
available arms in multi-armed bandit problems, our approach should utilize
microeconomic choice theory to infer indirect customer feedback through
strategical pricing experiments and incorporate such indirect information into
the pricing pipeline.

(c) Pricing performance monitoring. Being aware of potential market
environment shifts, our approach should build a statistical method-based
auditing pipeline to monitor the pricing performance to ensure the
transferability of the pricing decision mechanism in the current market
environment.

###  1.1 Main contributions

We summarize the knowledge advancement of this work contributing to existing
bandit-based dynamic pricing algorithm design (that learns a stationary-
environment-optimal pricing policy without awareness of potential market
environment change):

(I) ACIDP non-stationary dynamic pricing algorithm. (Figure 1, left) We
deliver the Actor-Critic Information Directed Pricing (ACIDP) algorithm that
learns profit-maximizing price via incomplete demand information and is able
to transfer pricing optimality in the presence of market environment shift.
The key of pricing mechanism transfer ability inside ACIDP is to construct the
Multi-Universe, a space of synthetic bandit environments shaped by environment
exploration, exploitation, and experimentation. By evaluating the expected
profit and demand information in each universe of Multi-Universe, we adopt the
Bayesian rule to maintain a posterior belief distribution over universes to
implement the well-known information directed sampling (IDS) [Russo and Van
Roy, 2018] for pricing decision. Then, we develop an auditing pipeline to
ensure pricing optimality transferability.

(II) Transferability auditing pipeline (Figure 1, right) We design a
transferability auditing pipeline to monitor market environment changes and
inform pricing agents if the credibility of the learned consumer demand model
is no longer accurate enough to inform profit-maximizing price. The auditing
pipeline consists a 3 stage sequence of events: yellow card (credibility
inspection; Section 3.3.A), audit sampling (optimality inspection; Section
3.3.B) and red card (transfer-ability inspection; Section 3.3.C). This
auditing pipeline contributes a novel framework in dynamic pricing literature.

(III) Empirical results. Via a combination of synthetic market environments
(stationary, structure shift, upside-down and real-world scenario), we show
the success of ACIDP is rooted in (a) benefits of synthetic bandit
environments and (b) benefits of auditing pipeline. The empirical results
support the superiority of ACIDP over the existing bandit-based pricing
method. We show the established environment synthesis pipeline and environment
auditing pipeline leads to substantial regret reduction across different
market environment shifts.

###  1.2 Related works

Bandit-based dynamic pricing and demand learning. Dynamic pricing is
acknowledged to be challenging without knowing demand function [Besbes and
Zeevi, 2009]. While MAB offers a cutting-edge partial monitoring setup[Cohen
and Treetanthiploet, 2021, Chen, 2021], bandits literature on dealing with
correlated and non-stationary rewards are still far from practical use.[Gupta
et al., 2018, Besbes et al., 2014, Slivkins and Upfal, 2008, Gupta et al.,
2020]. Our framework is based on [Misra et al., 2019], where an upper
confidence bound-based dynamic price experimentation policy was proposed under
the stationary assumption and extends MAB to microeconomic choice theory. Our
work further investigates the performance of Thompson sampling and Information
Directed Sampling and identified the transfer inability in these methods when
the market environment shifts. Our work adds to the dynamic pricing literature
by developing a non-stationary pricing method.

Bandit algorithms and Information directed sampling. Information directed
sampling (IDS) [Russo and Van Roy, 2018] is the state-of-the-art bandit policy
design principle. While IDS finds several applications in bandit learning
literature Kirschner et al. [2020, 2021], it remains open in the literature of
dynamic pricing. Intuitively, IDS could utilize information structures of
dynamic problems such that sampling one price can inform the pricing agent’s
assessment of other prices. Our work contributes a new bandit problem with
non-stationary rewards and a novel implementation of IDS in dynamic pricing
with optimality auditing.

Online hypothesis testing and confidence sequence. Our auditing procedure
borrows the modern and classical statistical tools: martingale confidence
sequence and hypothesis testing. The yellow card test in our auditing pipeline
[Maillard, 2019, Howard et al., 2020, 2021] gives generic construction of
martingale confidence sequence, which is a suitable statistical tool to alarm
environment shift. For the red card test in our auditing pipeline, we adopt an
exact test that quantifies the statistical significance of deviations from a
theoretically expected distribution of observations using sample data. Such
property conforms to the need of identifying the fitness of the demand curve.
Our work contributes to statistics literature with an innovative application
as an auditing pipeline.

###  1.3 Problem formulation and notation

This section defines dynamic pricing under partially identified demand
learning in Misra et al. [2019].

(I) Price, its demand, and its profit. At pricing step, the agent choose the
price $a$ from a finite set of $K$ prices
$\left\\{a_{1},\ldots,a_{K}\right\\}$. Each price $a$ associates with its true
demand $D(a)$, which is unknown and to be learned during the dynamic pricing
process. The true profit of price $a$ is defined as $R(a)=aD(a)$.

(II) Batch pricing experiment, pricing policy and observed demand/profit. We
assume prices can change after every $N$ consumers who visit the product. That
is, each pricing step consists of a batch of $N$ consumers. A dynamic pricing
algorithm, $\Psi$, selects prices based on the history of past prices and
earned profits; formally, given the filtration
$H_{\tau}=\left\\{a_{\tau},d_{\tau,a_{\tau}}\mid\tau=1,\ldots,t-1\right\\}$,
$a_{t}=\Psi\left(H_{\tau}\right)$. The observed demand $d_{t}(a_{t})$ is the
observed number of purchase after offering price $a_{t}$ at pricing step $t$;
formally, the observed demand is defined as
$d_{t}(a_{t})=\sum_{i=1}^{N}I(v_{i,t}\geq a_{t})$, where $v_{i,t}$ is the
valuation the $i$th customer in current pricing batch willing to pay and the
consumer make purchase if and only if the offered price $a_{t}$ is not greater
than $v_{i,t}$. The observed profit of price $a_{t}$ is $r_{t}(a_{t})\equiv
a_{t}d_{t}(a_{t})$.

(III) Objective of dynamic pricing policy. Our goal is to design pricing
policy $\Phi$ such that the offering price sequence $a_{1},a_{2},\cdots,a_{T}$
maximize the cumulative observed profit
$\sum_{t=1}^{T}r_{t}(a_{t})=\sum_{t=1}^{T}a_{t}d_{t}(a_{t}).$ And in bandit
terminology, the performance is measured by minimizing the regret
$\Delta_{T}(\Phi)=\mathbb{E}[\sum^{T}_{t=1}r_{t}(a^{*}_{t})]-\sum_{t=1}^{T}r_{t}(a_{t})$
where $a^{*}_{t}=\arg\max_{a\in\\{a_{1},\cdots,a_{K}\\}}R(a)$ is the optimal
price at $t$ that maximizes the profit.

##  2 Dynamic Pricing in Non-stationary Environment

Figure 1: ACIDP:Actor-Critic Information-Directed Pricing.

We assume at time $t$ underlies a customer valuation distribution such that
$v_{i,t}\overset{i.i.d.}{\sim}f_{V_{t}}$. The market environment shifts when
$f_{V_{t+1}}\neq f_{V_{t}}$. The shifting moment and transformation is assume
to be unknown. This section elaborates dynamic pricing problems in the
presence of such environment shifts from three perspective: desideratas,
challenges and our resolutions. Section 2.1 depicts the three desideratas of
dynamic pricing algorithms: (a) credibility, (b) optimality and (c) tranfer-
ability. Section 2.2 identifies the three major challenges from market
environment shifts: (a) credibility degradation, (b) optimality disruption and
(c) transfer inability. Section 2.3 delivers our framework that resolved these
challenges: (a) universe synthesizer (b) information-directed pricing and (c)
pricing strategy auditing.

###  2.1 Desiderata of pricing algorithms

Our goal is to design a pricing algorithm $\Psi$ that monitors the market
environment in order to (I) evaluate the optimality of earned profit of the
current pricing policy $\Psi$, and (II) audit the pricing policy $\Psi$
“transferability“ by testing whether the current learned consumer demand curve
sufficient to offer optimal pricing. In order for the pricing algorithms
$\Psi$ to fulfill the evaluation and auditing tasks, it must satisfy the
following desiderata: (I) it should be able to identify optimal price
distribution shift through statistical measures of earned profit, and (II) it
should be decision-wise computable, i.e., we should be able to tell if any
given individual pricing decision is no longer optimal due to market
environment shift.

Having outlined the desiderata for dynamic pricing policy, we now propose
three qualities that the policy $\Psi$ should be equipped with. $\Psi$ falls
behind if it fails to fulfill all of the three qualities corresponding to the
challenges depicted. These qualities are:

  1. 1.

Credibility–the learned demand model covers real consumer behavior from the
market environment. A credible learned demand model should resemble
“realistic“ consumer transaction behavior.

  2. 2.

Optimality–the pricing decision are greedy enough to earn the best-possible
profit, i.e. a pricing algorithm should be able to offer a near-optimal price
as if the true consumer demand model is available.

  3. 3.

Transferability–the pricing mechanism should not degenerate confronting market
environment shifts, i.e., algorithms that converge to stationary environment
optimal price is not truly ”transferable”.

###  2.2 Challenges from market environment shifts

Thinking in Bayesian language, the three modes of inabilities correspond to
defection in posterior (A. model credibility degradation), likelihood (B.
price optimality disruption), and prior (C. monitor transfer inability).

A. Model credibility degradation. (Posterior) The market environment shifts
drive changes in demand curves. Traditional stationary policies models
uncertainty of the environment on separate arms with the underlying assumption
that all arms share a single static environment. However, that means the
uncertainty of each arms’ result needs to be updated separate. Thus, the
performance is injured while judging against the truth basing on biased
information. In 4, we show how policies behave differently going from a static
environment to a dynamic environment. For instance, in periodic market shifts
(Case4), UCB and TS only recognize optimal price at the beginning of the
period as they are dragged by earlier faith.

B. Pricing optimality disruption. (Likelihood) The shifted demand curve also
changes the optimal price. Once the environment shifts, the likelihood of
demand that the algorithm had been exploiting is obsolete, uninformative to
inferring the shape of the profit curve. Such misinformation results in
selecting sub-optimal prices, vandalizing the optimality of pricing policy.

C. Monitoring Transfer inability. (Prior) Our current belief on the nature
affects our decision. While Transfer-ability is a common issue in machine
learning. failing to react to a new environment directly yields considerable
loss in dynamic pricing problems. If the market environment shift is
confirmed, then resetting belief is necessary for a valid non-stationary
algorithm, enhancing the credibility of modeling and reinforcing the
optimality of pricing. Contrarily, stationary policies jump into wrong
conclusions in upwards trend and become inconclusive in downwards trend. See
demonstration in Section 4.2.

###  2.3 Resolutions to non-stationary dynamic pricing

A. Enhance credibility by universe synthesizer. Section 3.1 The universe
synthesizer aids information-directed pricing by consistently providing
bountiful bandit environments to explore from. We identify three data sources.
1. Direct samples that are costly but effective. 2. Past data that are useful
but not necessarily accessible. 3. Synthetic data that expands the previous
two and does not require additional exploration. The universe synthesizer is
in charge of allocating the least rounds by manipulating the resources and
offer IDP as much information as possible.

B. Pursue optimality via information-directed pricing. Section 3.2 implements
information-directed sampling. ACIDP strikes a balance between expected regret
and expected information gain of each price. In Bayesian formulation, we model
the above-discussed universes as a random variable $\theta$ each, such that
conditioned on $\theta$, $d_{\tau}$ is an iid sequence. $p(\theta)$ not only
helps capture our belief that reflects the true nature, but allows ACIDP to
quantify the expected regret and mutual information between $a^{*}$ and
$d_{\tau}$.

C. Monitor transferability via pricing strategy auditing. Section 3.3 Price
auditing assesses a firm’s price policy. It helps ensure that prices offered
are aligned with the consumer’s willingness to pay. The audition consists of:
a martingale sequence prescreening, an $\epsilon$-greedy based explorer, and a
diagnostic test. The first one detects the anomaly and summons the universe
synthesizer to expand resources while exploring a little with
$\epsilon$-greedy. Lastly, the aforementioned exploration helps diagnose
environmental changes via hypothesis testing.

##  3 Methodology

Actor-Critic Information-Directed Pricing (ACIDP) Algorithm 1 presents our
solution, the Actor-Critic Information-Directed Pricing algorithm, to the non-
stationary dynamic pricing problems established at Section 2. There are 3 key
components in our design of ACIDP algorithms: Universe Synthesizer,
Information directed pricing, and Transferability Test. Section 3.1
establishes the Universe synthesizer to construct candidate universe to
capture system uncertainty of the market environment, as solutions to the
challenge 2.2.A. Section 3.2 illustrates how ACIDP explores the synthetic
environments supported by information directed sampling principle to maximize
the cumulative profit, as a solution of challenge 2.2.B. Section 3.3
elaborates the transferability test to audit environment stationarity that
allow ACIDP a quick reaction when face with environment shift, as a solution
of challenge 2.2.C.

1 for  _$t$ from 1 to $T$ do_ do

2 $\vec{\Delta}$, $\vec{g}$ $\leftarrow$ finiteIR$(L,K,N,p,q)$

3 $a_{t}$ $\leftarrow$ $a_{k}$, $k\in\arg\min_{k}$
$\vec{\Delta}_{k}^{2}/\vec{g_{k}}$

4 if  _alert = yellow card_ then

5 $q_{\theta^{C}}$ $\leftarrow$ Generator$(c)$

6 $p(\theta^{C}_{i})$ $\leftarrow$ $1$, $p(\theta)$ $\leftarrow$
$\frac{p(\theta)}{\Sigma_{\theta}{p(\theta)}}$

7 Sample $e\sim$ $bernoulli(\epsilon)$

8 if  _e=1_ then

9 $a_{t}$ $\leftarrow$ sequentially select sparse arms

10

11 end if

12

13 end if

14 if  _alert = red card_ then

15 $a_{t}$ $\leftarrow$ explore through $a_{1}$ to $a_{k}$

16 $q_{\theta^{P}}$ $\leftarrow$ Initiator($L^{P}$, n)

17

18 $p(\theta^{P}_{i})$ $\leftarrow$ $L$, $p(\theta)$ $\leftarrow$
$\frac{p(\theta)}{\Sigma_{\theta}{p(\theta)}}$

19 end if

20 offer price $a_{t,k}$ and observe $d_{t,a_{t}}$

21 alert $\leftarrow$ transferability test($d_{t,a_{t}}$)

22
$p_{t+1}(\theta)\leftarrow\frac{p_{t}(\theta)q_{\theta,a_{t}}(d_{t,a_{t}})}{\Sigma_{\theta^{\prime}\in\Theta}p_{t}(\theta^{\prime})q_{\theta^{\prime},a_{t}}(d_{t,a_{t}})}$

23 end for

24

Algorithm 1 Actor-Critic Information-Directed Pricing

###  3.1 Universe synthesizer

To exploit the indirect information between available prices, we model the
environment uncertainty via a set of universes $\theta$s. Each universe
$\theta$ associates a distinctive customer valuation distribution and
consequently a demand curve. Such association treats ”set of available prices“
as a fundamental modeling unit, instead of modeling the uncertainty of each
individual action as UCB and TS. Using the bayesian language, we further
defines the likelihood of observing $d\in 0,1,\dots,N,$ purchases when price
$a$ is set under the $\theta$ universe as $p(d|\theta,a)$. With some abuse of
notation, we denotes $p(d|\theta,a)$ as $q_{\theta,a}(d)$ and let $q$ be the
likelihood of all possible outcomes corresponds to the proposed price as a
whole. Mathematically, $q$ is a $L\times k\times(N+1)$ vector.

Universe synthesizer provides the likely bandit environments $\Theta$ =
{$\theta:1,2,...,L\\}$ and $q_{\theta}$. $p(\theta)$ captures the belief about
the true nature of the system. While $q_{\theta}$ do not update on the fly,
$\Theta$ can be expanded and include more appropriate $q_{\theta}$. As a
result, demand curve is learned by updating the belief on all universes, and
the information obtained from calculating the posterior can be shared by all
arms. Hence, ACIDP could transfer to a new environment agilely.

There are three source of bandit environments involved: Perceived universes
(environment exploration), Vintage universes (environment exploitation), and
Counterfactual universes (environment experimentation). For simplicity, we
denote ${\Theta}={\Theta^{P}}\cup{\Theta^{V}}\cup{\Theta^{C}}$ and
$L=L^{P}+L^{V}+L^{C}$.

A.Perceived universes (environment exploration). In finite set IDS, $q$ is
treated as a known input. Cases such as new product launch, however, do not
guarantee $q$ to be known. Perceived universe generalize $q$ by learn-then-
IDS. Algorithm 2 samples $n$ times from each price $a$ and summarize the
empirical likelihood as $q_{\theta^{P}}$. Number of repetitive sample $n$ and
increment perceived universes $L^{P}$ are left as hyperparameters. This naive
method consumes $L^{P}*K*N*n$ customer exploration. Particularly, $N*n$ are
the sample size for an atomic estimation of $q_{\theta,a}$.

1for  _i = 1 to $L^{P}$_ do

2 for  _1 to n_ do

3 for  _a = $a_{1}$ to $a_{k}$_ do

4 Sample $a$ and collect observation $d_{a,n}$

5

6 end for

7

8 end for

9 $q_{\theta^{P_{i}},a}(d)$ $\leftarrow$ $\frac{1}{n}\Sigma_{n}I(d_{a,n}=d)$
$\forall d,a$

10

11 end for

Return $q_{\theta^{P}}$

Algorithm 2 Initiator($L^{P}$, n)

Remark. If $n>1$, we encourage first loop through $K$ then $n$ to avoid
inconsistent estimation across $a_{k}$ within a single universe when non-
stationarity presents. Besides, zero probability needs to be replaced with a
tiny number for unobserved events for computational consideration.

B.Vintage universes (environment exploitation). Given past data, or prior
belief, we could prepare them as $q_{\theta^{V}}$ and $p(\theta^{V})$ as
discussed. Such source would then be checked by Bayesian updating or refined
through counterfactual universes.

C.Counterfactual universes (environment experimentation) Computing $q$ with
pure Monte Carlo methods could reduce inevitable regret from exploration.
Nonetheless, it may took unlimited guess and is computationally inefficient.
Algorithm 3 implements such spirit by integrating previous universes to
estimate $D(a)$ and $f_{V}$ to generate diverse universes $\theta^{C}$,
$q_{\theta^{C}}$. Counterfactual universe are generally cost-friendly and
could conspicuously extend the previous two sources.

1$D(a)=\Sigma_{\theta}\Sigma_{d}p(\theta)p(d|\theta,a)d/N$, $\forall a$

2 $\bar{a_{k}}=\frac{a_{k}+a_{k+1}}{2},k=1,2,\dot{,}k-1$

3 $p(V^{\prime}=\bar{a_{k}})$ = $D(a_{k})-D(a_{k+1})$, $k=1,2,\dot{,}k-1$

4 for  _$c_{i}$ $\in$ $[-a_{k},a_{k}]$_ do

5 $f_{V^{C_{i}}}\sim p(V^{\prime})+c_{i}+\xi$, where $\xi\sim
N(0,\sup\\{\bar{a_{k}}\\})$

6 for  _$j=1\ to\ n$_ do

7 sample $v^{C_{i}}_{j}$ from $f_{V^{C_{i}}}$

8 end for

9 $q_{\theta^{C_{i}},a}$ $\leftarrow$ $p(\Sigma^{n}_{j=1}I(v^{C_{i}}_{j}\geq
a)=d)$, $\forall$ $d,a$

10

11 end for

Return $q_{\theta^{C}}$

Algorithm 3 Generator(c)

In Algorithm 3 (visualized in appendix 12), line1 estimates the demand curve
by calculating the posterior predictive distribution and normalize all
components into $[0,1]$ by dividing $N$. Line2 uses the midpoint of price
intervals to estimate valuation distribution. Since we can only observe the
realized demands that associates with the available price sets $\\{a_{k}\\}$,
the domain of $d(a)$ is hence discrete and unlike the underlying valuation
distribution $f_{V_{t}}$. Line2 uses the midpoint for a naive interpolation.
Namely, say $D(0.5)=0.4$ and $D(0.6)=0.3$, we conclude that there are $10\%$
of customers holds a valuation near $0.55$. Line3 derives a discrete
approximation of $f_{V_{t}}$ using midpoints $\\{\bar{a_{k}}\\}$. Line4 then
decorates the final approximate $f_{V^{C}}$ by applying noise $\xi$ and
intended manipulation $c$. The noise creates a smooth continuous texture and
is responsible for neutralizing the sampling error with randomization. $c$
could be any known manipulation. Line 5 demonstrates a simple linear
transformation within the price range. Line6 samples from the artificial
valuation distribution $f_{V^{C_{i}}}$ to construct empirical likelihood
$q_{\theta^{C_{i}}}$.

Overall, online samples, historical data and synthetic data are main resource
of information. ACIDP collaborate with all of them and functions as an
ensemble method. In the Bayesian inference phase, the belief is updated
recursively and each source are assigned with a distinct weight by the
posterior distribution to maintain credible bandit environment.

Remark. In practice, one should initialize higher prior on $\theta^{P}$ to
reflect the authenticity. Besides, we encourage setting a tiny lower bound for
$p(\theta)$ such that the universe wouldn’t be completely ruled out by
Bayesian update. 4 Case 4, 5 exemplify that old $\theta s$ are recyclable and
could benefit decision-making.

###  3.2 Information-directed pricing

The information-directed pricing ensures the optimality by lowering expected
regret and gaining information as much in a single period. While Beta-
Bernoulli bandit is feasible for binary purchase result, we suggest that
finite setting is more flexible and computationally convenient. The likelihood
$q_{\theta}$ could be designed to capture specific relation in prices such as
correlation and monotonicity, and it does not rely on parametric prior and
likelihood distributions. IDP optimize the price by exploring the multi-
universe $\Theta$. There are three steps covered in IDP.

A. Estimate Regret and Information Gain Conditioned on universe $\theta$, the
next observation $d_{t}(a_{t})$ given price $a_{t}$ is estimated by
$q_{\theta,a_{t}}(d)$. The prior $p(\theta)$ denote the belief of the universe
$\theta$. Let $\Theta_{a}$ denotes the collection of universes $\theta$ that
the price $a$ is the optimal price where the optimal price $a$ is the price
that maximize the expected profit $\sum_{d}q_{\theta,a}(d)r_{a}(d)$ of
offering price $a$. Thus, the optimality of price $a^{*}$ can be described by
$p(a^{*})=\sum_{\theta\in\Theta_{a^{*}}}p(\theta)$. Here, we further define
the expected regret by the gap from optimal aggregate profit of offering price
a $R^{*}-\sum_{\theta}p(\theta)\sum_{d}q_{\theta,a}(d)r_{a}(d)$, where $R^{*}$
is the possible expected optimal reward. Finally, we use the the mutual
information $I(a^{*},d)$ =
$\sum_{a^{*},d}p_{a}\left(a^{*},d\right)\log\frac{p_{a}\left(a^{*},d\right)}{p\left(a^{*}\right)p_{a}(d)}$
to measure the expected information gain. $p_{a}(d)$ is the aggregate demand
distribution of price $a$ and $p_{a}(a^{*},d)$ is the aggregate price-demand
joint distribution inside $a^{*}$-universes. Algorithm 4 summarizes the
complete process.

1 $\Theta_{a}$ $\leftarrow$
$\\{\theta|a=\arg\max_{a^{\prime}}\Sigma_{d}q_{\theta,a^{\prime}}(d)a^{\prime}d\\},\forall\theta$

2 $p(a^{*})$ $\leftarrow$ $\Sigma_{\theta\in\Theta_{a^{*}}}p(\theta),\forall
a^{*}$

3 $p_{a}(d)$ $\leftarrow$ $\Sigma_{\theta}p(\theta)q_{\theta,a}(d),\forall
a,d,\theta$

4 $p_{a}(a^{*},d)$ $\leftarrow$
$\frac{1}{p(a^{*})}\Sigma_{\theta\in\Theta_{a^{*}}}q_{\theta,a}(d),\forall
a,d,a^{*}$

5 $R^{*}$ $\leftarrow$
$\Sigma_{a}\Sigma_{\theta\in\Theta_{a^{*}}}\Sigma_{d}p(\theta)q_{\theta,a}(d)ad$

6 $\vec{g_{k}}$ $\leftarrow$
$\Sigma_{a^{*},d}p_{a}(a^{*},d)log\frac{p_{a}(a^{*},d)}{p(a^{*})p_{a}(d)},\forall
a$

7 $\vec{\Delta_{k}}$ $\leftarrow$
$R^{*}-\Sigma_{\theta}p(\theta)\Sigma_{d}q_{\theta,a}(d)ad,\forall a$

Return $\vec{\Delta}$, $\vec{g}$

Algorithm 4 FiniteIR(L, K, N, p, q)

B. Optimize with Information Ratio Intuitively, minimizing the square of
expected regret divided by expected information gain balance between the
reward and information trade-off. The information ratio is defined as
$\Psi_{t}(\pi)=\pi^{T}\Delta^{2}/\pi^{T}g$ where $\pi$ denotes the a
k-dimensional action distribution vector and IDP then choose a price according
to

$\pi^{IDP}\in\arg\min_{\pi}(\pi^{T}\Delta)^{2}/\pi^{T}g$

for monotone price sets, it is sufficent to pull the action with

$a_{k}\in\arg\min_{k}\Delta_{k}^{2}/g_{k}$

C. Update universes belief Lastly, we update the belief on universes with new
observation by

$p_{t+1}(\theta)\leftarrow\frac{p_{t}(\theta)q_{\theta,a_{t}}(d_{t,A_{t}})}{\Sigma_{\theta^{\prime}\in\Theta}p_{t}(\theta^{\prime})q_{\theta^{\prime},a_{t}}(d_{t,a_{t}})}$

This step is vital for adaptation when confronted with environmental shift.
While the goal of Information Ratio is to figure out the optimal price (ensure
optimality), Bayesian update is more concerned with unveiling the true
environment (maintain credibility). They interact with each other to settle on
the ultimate solution.

###  3.3 Pricing strategy auditing

Stationary bandit algorithms struggle in non-stationary as their convergent
decision blinded them from environmental changes. Interestingly, it forms
another exploration-exploitation trade-off to check stationarity. Only when
the present set of $\theta s$ no longer applies should transferability test
allow the ACIDP reinitialize its belief. Otherwise, manageable shifts should
first be addressed by recruiting additional counterfactual universes and
Bayesian update. ACIDP accomplish this by classifying the environmental
changes into three states: no change, slight change, huge change. It is like
there are two levels of alert in ACIDP for non-stationarity: Yellow Card and
Red Card. The alert and the accompanying measure are specified as the three
steps below. Algorithm 5 summarizes the framework. The first step start from
line1 to line7; second at line8; the rest for final step. Here $w$ is a
hyperparameter representing the maximum number of lastest periods considered
contemporary, and the newest decision will based on observation found in the
$w$-period rolling window.

1$W_{\tau}$ $\leftarrow$ $\\{d_{\tau,a_{\tau}}:d_{\tau,a_{\tau}}\in
H_{\tau},t\geq\tau\geq t-w\\}$

2 $W_{\tau,a_{t}}$ $\leftarrow$
$\\{d_{\tau,a_{t}}:d_{\tau,a_{\tau}=a_{t}},d_{\tau}\in W|a_{t}\\}$

3 $\\{d_{i}\\}^{m}_{i=1}$ $\leftarrow$ reindex $W_{\tau,a_{t}}$

4 $\bar{d}$ $\leftarrow$ $\frac{\Sigma^{m}_{i=m-n}d_{i}}{n}$, $X$ $\leftarrow$
$\Sigma^{m-n}_{i=1}\frac{d_{i}-\bar{d}}{N/2}$

5 $LB$, $UB$ $\leftarrow$ $\frac{X}{m-n}$ $\pm$ $1.7$
$\sqrt{\frac{loglog(2t)+0.72log(10.4/\alpha_{1})}{t}}$

6 if  _ $LB>0$ or $UB<0$ _ then

7 alert $\leftarrow$ yellow card

8 if  _e=1 (follows from line7 in algorithm1)_ then

9
$pvalue=binomial(d_{t,a_{t}},N,\Sigma_{\theta}p(\theta)p_{\theta,a_{t}}(d)d/N)$

10 if  _$pvalue$ $<$ $\alpha_{2}/n$_ then

11 alert $\leftarrow$ red card

12 else

13 $\epsilon$ $\leftarrow$ $\epsilon*r_{decay}$

14 end if

15

16 end if

17

18 end if

Return alert

Algorithm 5 Transferability Test($d_{t,a_{t}}$)

A. Martingale Test for stationarity. (Yellow card: Demand model credibility
inspection) In each round, the martingale sequence test compares the empirical
mean of most recent $n$ $d_{\tau,a_{\tau}=a_{k}}$ with the earlier $m-n$
within $w$ periods with confidence level $\alpha_{1}$. Line1 gives the latest
$w$ period data from filtration $H_{\tau}$, from which we filter out $m$ of
those associated with same price as $a_{t}$. Line4 reallocate the observation
into latest $n$ and not as latest $m-n$. $X$ is the test statistic measuring
the deviation of the two ordered sequence, and 2 in denominator is the
recommended adjustment for binomial distribution according to Howard. Line5
then move on to test the deviation of the two sequence, $LB$ denotes lower
bound, $UB$ denotes upper bound (equation 2 in [Howard et al., 2021]). A
yellow card alarms ACIDP when anomaly detected. Yellow Card first summons
Generator for possible environment changes. Besides, an $\epsilon$-auditor is
on standby to sample and execute diagnostic inspection with probability
$\epsilon$.

B. $\epsilon-$auditor sampling (Verification: Price mechanism optimality
inspection) With $\epsilon$, $\epsilon-auditor$ explores the unfamiliar arms
and collects evidence for non-stationarity; otherwise, IDP keeps exploiting on
what it has. For diagnostic tests, it is usually sufficient to sample the
quartiles over the price range. So the regret do not necessarily grow with K.
In practice, the auditor is activated after $p(\theta)$ converged to ensure
the upfront change is unpredictable and $D(a)$ has stopped improving from
existing knowledge. The $\epsilon$ decays by $r_{decay}$ when the diagnostic
tests are not rejected, and resets whenever receives another yellow card.

C. Demand Deviation test. (Red card: Optimal price transferability inspection)
Here, one could adopt correspondent hypothesis testing techniques that suits
the observation structure. In our setting we conduct binomial tests with
$binomial(d_{t,a_{k}},N,\Sigma_{\theta}p(\theta)p_{\theta,a_{k}}(d)d/N))$ on n
prices collected by $\epsilon-$auditor with Bonferroni corrected confidence
level $\alpha_{2}/n$. If the test is rejected in arbitrary price, we conclude
that the current demand belief is obsolete. This may indicates both external
or internal errors, i.e. 1. the environment has changed, or 2. a larger sample
size is required for credibility and optimality. In either way, the Initiator
will be triggered and facilitates exploration.

##  4 Experiments

This section discusses the computational findings of our proposed method. We
highlighted simulations that covers six distinct common situations and an
real-life example with corporate data. We begin by simulating the well-studied
stationary MAB pricing scenario. On to some non-stationary bandit settings
with structural shifts, four scenarios are examined: rapid growth, rapid
decline, seasonality, and volatility. Next, we consider an upside-down move in
market environment where we suppose the shift is fully unanticipated. Finally,
we implements ACIDP in real customer data.

We adapt the experiment design from [Misra et al., 2019]. The following data
generation processes are identical in six simulation. Customers arrive, notice
the price, and only purchase if their valuation $v_{i,s}$ exceeds the price.
All policies revise the pricing every N=10 customers, so $d_{t}\in{0,1,..,10}$
purchases. Customers are assumed to come from 1000 distinct equal-sized
segments that holds distinct valuation
$\\{v_{s}\\}^{1000}_{s=1}\overset{i.i.d}{\sim}Beta(3,6)$ which is a right-
skewed distribution. Besides, we consider heterogeneity within the segments by
$v_{i,s}=v_{s}+e_{i},e_{i}\sim N(0,0.1)$. We consider this setting as the
beginning customer valuation $f_{V_{0}}$, and valuation distribution
$f_{V_{t}}$ will evolve from this baseline as time goes (except Case 3).

All policies are unaware of the $f_{V}$, the shifting moments and magnitude.
Furthermore, $v$ is not directly observable. The agent must learn the demand
curve under partial monitoring and choose from the price set $p\in[0.01,1]$
with $K=20$ prices evenly spaced to minimize regret. All cases are subjected
to a $T=2000$ horizon and ten independent repetitive trials. Along with ACIDP,
we also implement UCB family, TS and EG, policies that do not require T as
known. We have attempted to delineate the implemented policies are optimized
for the simulated horizon.

Figure 2: Mean Regret Under Stationary, Structural Non-stationary, Upside-Down
Non-stationary . Figure 3: Price Selection Sequence Under Stationary,
Predictable Non-stationary, Unpredictable Non-stationary (All Trials)

###  4.1 Stationary environment

Case1: Stationary Environment Under stationary conditions, candidates appear
to explore adequately and are capable of recognizing the true optimal price.
Note that ACIDP-$\theta$ has a somewhat greater mean regret when L=2 and n=1.
It result from observing outliers upon calculating empirical mean in perceived
universes in a single trial, which also explains why IDS with L=4, n=1 yields
a higher mean and perform robustly across trials. In general, we demonstrated
that, despite accruing fixed initialization cost, learn-then-IDS is still
competitive with various alternative policies in stationary bandit settings.

###  4.2 Structural Environment Shifts

Case2: Rapid Growth. In the second case, the $V$ distribution experience a
rapid growth of 0.3 at t=1001. i.e. $V_{1},V_{2},\dots,V_{1000}\sim
f_{V_{0}}$, and $V_{1001},V_{1002},\dots,V_{2000}=V_{1000}+0.3$. This setup
can be compared to the effect of governmental revitalization, in which all
customers received the same level of subsidy.

When confronted with upward adjustments, TS and UCB typically cease exploring
immediately and converge on $a_{1000}$ because they believe that their choice
has started to proper even more without comparing the growth in other options.
Thus, their regret grows linearly after t=1000. As for ACIDP, this slight
change is easily detected by the martingale tests and resolved by the
counterfactual universes.

Case3: Rapid Decline. The third case is the reverse counterpart of case2. It
starts at $V_{1}=V_{0}+0.3,V_{0}\sim f_{V_{0}}$ and the valuation drops to
$V_{1001},V_{1002},\dots,V_{2000}\sim f_{V_{0}}$. The purpose of adopting such
design is to allow clear comparison with case2.

Though the expected cumulative optimal rewards are identical in Case2 and
Case3, the performance of UCB family plummets in Case3. It shows clear defect
in the optimistic decision. Optimistic decision becomes determinant and
overconfident when facing upwards trends while being indecisive when facing
downwards shifts. Nevertheless, ACIDP excels in both cases.

Case4: Seasonality. The fourth case considers the presence of a periodic shift
such that $V_{t}=V_{0}+0.3\sin(4t\pi/T),V_{0}\sim f_{V_{0}}$. The purpose of
this example is to simulate the seasonality in customer preferences or market
trends.

This case showcases the pivotal role of generator and IDP. Alternatives such
as epsilon-greedy may be able to reinvigorate to sudden structural changes
thanks to randomized checks, these checks are too inefficient to recover from
recursive or continuous changes. In a periodic non-stationary environment, the
perceived total environmental shifts offset over time, rendering alternatives
ineffective. Alternatives relies on a single global mean estimation, so the
mean returns to the bench mark after a cycle of environmental changes. ACIDP,
on the other hand, discovers the optimal arm by first recording each presence
in universes. Appeared universes could then be restored and recycled, which
explains why sin function curve (shown in appendix 8) becomes more defined in
the later phase.

Case5: Volatility. In the fifth case, we consider $f_{V}$ with volatile
structural shifts dependent on t. We take an one-dimensional Brownian motion
$\\{B_{t}\\}_{T\geq t\geq 1}$ and shift $V_{t}=V_{0}+B_{t}$ by
$B_{t}=B_{t-1}+\xi/\sqrt{T}$, where $\xi\overset{i.i.d.}{\sim}N(0,1)$. Given
the independence of the movements in each round, we postulated that the safest
strategy to minimize regret is to price at $a^{*}_{t-1}$ $\forall t>1$ as
$\mathbb{E}[B_{t}]=B_{t-1}$. As a result, the policy must respond quickly and
robustly in light of the filtration.

ACIDP adapts gracefully to the volatile environment. It is sensitive to minute
changes and respond precisely. Again, this volatile example is associated with
a possible shift offset. Specifically, the range of $V$ experiences a similar
peak at around the $700^{th}$, $1050^{th}$, and $2000^{th}$ period in this
sequence. Not only did ACIDP modify its prices to reflect the fluctuation
throughout the stochastic sequence, it maintained constant during these
upswings. Such robustness is a desirable characteristic in dynamic pricing.

###  4.3 Upside-down Environment shift

Case6: Distribution Shift. In the last synthetic scenario, we investigate an
extreme example in which the hidden value distribution changes unexpectedly.
At t=1000, the population distribution of segment mean set
${v_{s}}^{1}000_{s=1}$ transforms from a right-skewed $beta(3,6)$ to a bimodal
$beta(0.9,0.5)$ with a greater mean and variance. We also let the mean
difference between the two distributions to be similar as case 2.

After $1000^{th}$ round, only ACIDP have identified the true optimal arm;
other policies’ regrets grow linearly with time. Additionally, we establish
that, while ACIDP is capable of acting in near-optimal directions without
transferability test, it does not recognize the global optimal arm. The
regular ACIDP with transferability test learns the new optimal arm through the
recruitment of new universes, the last resort of transferability test, whereas
the ACIDP-window proposed in appendix A progressively transitions to the new
optimal through online fine-tuning its existing universes.

###  4.4 Real-Life Data

Finally, we test our algorithm in a realistic scenario with Criteo Sponsored
Search Conversion Log Dataset [Tallis and Yadav, 2018]. Criteo is a French
online advertising firm. The data are collected from August to November 2018
and covers price, ad clicks, and conversion records for several products. We
consider a non-stationary bandit pricing problem where during the pricing
horizon, the e-commerce platform mistook the product information of A with
another product B on the webpages, and the agents are required to fix the
price tag automatically to avoid potential loss.
To begin, we selected three of the most popular products across a range of
pricing points, and were able to model the demand curve of them based on the
real data. From low to high price levels, we have product A, B, C with optimal
prices €70, €150, and €280 respectively.
The experiment lasted for T=6000 rounds in total; initially, the agents were
asked to price product B based solely on conversion rate. At t=2000, the page
was mistaken with product C and thus the original price tag seemed too
appealing. The regret may increases dramatically if the price was not adjusted
accordingly. Similarly, at t=4000, the page was again mislabeled with
information of product A. In this case, the prices are expected to go from
€150 to €280 then €70.
The action set consists of ${a_{k}}^{5}0_{k=1}$ = ${10,20,...,500}$ $K=50$
prices, which are the price levels most products collaborated with Criteo at.
The price reset every $N=500$ clicks. The only information available each
round is the number of clicks that contribute to conversion. The policies are
tested with noisy conversions generated from $d_{t,a_{t}}\sim
binomial(N=500,D_{t,a_{t}})$, where $D_{t,a_{t}}$ is the true conversion rate
calculated from the dataset.
The result is align with the above findings. It showed that ACIDP is the only
policy capable of achieving optimality and pricing all three products rapidly
and accurately. The cumulative regret of ACIDP exhibited sub-linearity and id
significantly lower comparing to others. While most of the policies are
capable of recognizing the optimal price of product B, ACIDP’s success in
detecting the inability to transfer existing knowledge to price product A, C
at around $2000^{th}$, $4000^{th}$ round and activating the initiator to
retrain itself is what makes the transparent difference.

Figure 4: Regret and Price Selection (red line denotes $a^{*}$) in Real World
Data.

##  5 Conclusion and Future works

This article explores dynamic pricing in MAB with non-stationary rewards and
introduces a new algorithm, Actor-Critic Information-Directed Pricing. The
proposed method takes into account the presence external changes and exploits
regret-minimized prices while identifying market demand on the fly. We
investigate qualities that are absent in classical solutions concerning
dynamic pricing problems and address them by developing three core modules:
Universe Synthesizer, Transferability Test, and Information-Directed Pricing.
Universe Synthesizer deals with price correlation by assessing the common
source of demand and simulating possible futures in parallel universes. The
transferability test decomposes the non-stationarity in the environment into
three steps. First, Universe Synthesizer collaborates with IDP to deal with
controllable changes. A step further, ACIDP undergoes thorough exploration
once the current knowledge had been concluded outmoded. IDP embraces ensemble
and information-directed sampling techniques to estimate the best price from
the information presented in sources offered by the Universe Synthesizer.
These modules are empirically proved to outperform alternative policies that
are typically dominated by exploiting the empirical means in separate arms.

Questions remain unanswered. To begin, whether one could more efficiently
initiate $q$ in dependent arm scenarios. Secondly, as we aim to price
according to customer valuation, it’s worth researching whether ACIDP works
effectively when competition exists. Finally, one could further consider
heterogeneous variance across different segments. This may lead to a non-
uniform estimation error across the valuation.

## References

  * Auer et al. [2002] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2):235–256, 2002.
  * Besbes and Zeevi [2009] Omar Besbes and Assaf Zeevi.  Dynamic pricing without knowing the demand function: Risk bounds and near-optimal algorithms.  _Operations Research_ , 57(6):1407–1420, 2009\.
  * Besbes et al. [2014] Omar Besbes, Yonatan Gur, and Assaf Zeevi.  Stochastic multi-armed-bandit problem with non-stationary rewards.  _Advances in neural information processing systems_ , 27, 2014.
  * Chapelle and Li [2011] Olivier Chapelle and Lihong Li.  An empirical evaluation of thompson sampling.  _Advances in neural information processing systems_ , 24, 2011.
  * Chen [2021] Ningyuan Chen.  Multi-armed bandit requiring monotone arm sequences.  _Advances in Neural Information Processing Systems_ , 34, 2021.
  * Cohen and Treetanthiploet [2021] Samuel Cohen and Tanut Treetanthiploet.  Correlated bandits for dynamic pricing via the arc algorithm.  _arXiv preprint arXiv:2102.04263_ , 2021.
  * Garivier and Cappé [2011] Aurélien Garivier and Olivier Cappé.  The kl-ucb algorithm for bounded stochastic bandits and beyond.  In _Proceedings of the 24th annual conference on learning theory_ , pages 359–376. JMLR Workshop and Conference Proceedings, 2011.
  * Granmo [2010] Ole-Christoffer Granmo.  Solving two-armed bernoulli bandit problems using a bayesian learning automaton.  _International Journal of Intelligent Computing and Cybernetics_ , 2010.
  * Gupta et al. [2018] Samarth Gupta, Gauri Joshi, and Osman Yagan.  Exploiting correlation in finite-armed structured bandits.  _arXiv preprint arXiv:1810.08164_ , 2018.
  * Gupta et al. [2020] Samarth Gupta, Gauri Joshi, and Osman Yağan.  Correlated multi-armed bandits with a latent random source.  In _ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)_ , pages 3572–3576. IEEE, 2020.
  * Howard et al. [2020] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon.  Time-uniform chernoff bounds via nonnegative supermartingales.  _Probability Surveys_ , 17:257–317, 2020.
  * Howard et al. [2021] Steven R Howard, Aaditya Ramdas, Jon McAuliffe, and Jasjeet Sekhon.  Time-uniform, nonparametric, nonasymptotic confidence sequences.  _The Annals of Statistics_ , 49(2):1055–1080, 2021.
  * Kaufmann et al. [2012] Emilie Kaufmann, Olivier Cappé, and Aurélien Garivier.  On bayesian upper confidence bounds for bandit problems.  In _Artificial intelligence and statistics_ , pages 592–600. PMLR, 2012.
  * Kirschner et al. [2020] Johannes Kirschner, Tor Lattimore, and Andreas Krause.  Information directed sampling for linear partial monitoring.  In _Conference on Learning Theory_ , pages 2328–2369. PMLR, 2020\.
  * Kirschner et al. [2021] Johannes Kirschner, Tor Lattimore, Claire Vernade, and Csaba Szepesvári.  Asymptotically optimal information-directed sampling.  In _Conference on Learning Theory_ , pages 2777–2821. PMLR, 2021\.
  * Lai et al. [1985] Tze Leung Lai, Herbert Robbins, et al.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Maillard [2019] Odalric-Ambrym Maillard.  Mathematics of statistical sequential decision making.  2019\.
  * Maillard et al. [2011] Odalric-Ambrym Maillard, Rémi Munos, and Gilles Stoltz.  A finite-time analysis of multi-armed bandits problems with kullback-leibler divergences.  In _Proceedings of the 24th annual Conference On Learning Theory_ , pages 497–514. JMLR Workshop and Conference Proceedings, 2011.
  * May and Leslie [2011] Benedict C May and David S Leslie.  Simulation studies in optimistic bayesian sampling in contextual-bandit problems.  _Statistics Group, Department of Mathematics, University of Bristol_ , 11(02), 2011.
  * Misra et al. [2019] Kanishka Misra, Eric M Schwartz, and Jacob Abernethy.  Dynamic online pricing with incomplete information using multiarmed bandit experiments.  _Marketing Science_ , 38(2):226–252, 2019.
  * Russo and Van Roy [2014] Daniel Russo and Benjamin Van Roy.  Learning to optimize via posterior sampling.  _Mathematics of Operations Research_ , 39(4):1221–1243, 2014.
  * Russo and Van Roy [2016] Daniel Russo and Benjamin Van Roy.  An information-theoretic analysis of thompson sampling.  _The Journal of Machine Learning Research_ , 17(1):2442–2471, 2016.
  * Russo and Van Roy [2018] Daniel Russo and Benjamin Van Roy.  Learning to optimize via information-directed sampling.  _Operations Research_ , 66(1):230–252, 2018.
  * Russo et al. [2018] Daniel J Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, Zheng Wen, et al.  A tutorial on thompson sampling.  _Foundations and Trends® in Machine Learning_ , 11(1):1–96, 2018.
  * Scott [2010] Steven L Scott.  A modern bayesian look at the multi-armed bandit.  _Applied Stochastic Models in Business and Industry_ , 26(6):639–658, 2010.
  * Slivkins and Upfal [2008] Aleksandrs Slivkins and Eli Upfal.  Adapting to a changing environment: the brownian restless bandits.  In _COLT_ , pages 343–354, 2008.
  * Tallis and Yadav [2018] Marcelo Tallis and Pranjul Yadav.  Reacting to variations in product demand: An application for conversion rate (cr) prediction in sponsored search.  _arXiv preprint arXiv:1806.08211_ , 2018.
  * Thompson [1933] William R Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ , 25(3-4):285–294, 1933.

##  Appendix A Alternative Design

###  A.1 Variant of ACIDP

Moving-window Transfer An alternative design of a transferable bandit
algorithm assumes the newest the best. In algorithm 6, we present a method
that evolves without hypothesis testing and additional exploration. This
algorithm works well when each shifted stage lasts for a sufficient amount of
time. Let $\theta^{w}$ be a specialized counterfactual universe that updates
itself constantly. $\theta^{w}$ learn from others’ experience and overwrites
recent pulled price in $q_{\theta^{w}}$ with latest samples. Since such
manipulation may violate the law of non-increasing demand over ordered prices.
So in line 9, assuming $a_{k}<a_{k+1},\forall k$, we correct it by the
estimates of adjacent prices. The recorded likelihood will be inherited
proportion to the posterior $p(\theta^{w})$, i.e. if such update is indeed
plausible, the $\theta^{w}$ will dominates $\Theta$ and reproduce itself in
the next round. Ideally, ACIDP-window selects a monotone pricing sequence till
they reach the near-optimal arms. The hyperparameter $W$ controls the transfer
speeds in this case. This approach sometimes outperforms ACIDP as it does not
require additional exploration. (Shown in Simulation Case 6) Intuitively, the
algorithm updates the likelihood by assuming recent samples are truth and
normalization gradually dilute the weight of older samples and transfer
$q_{\theta^{w}}$ into the new environment.

1$W_{\tau}$ $\leftarrow$
$\\{a_{\tau},d_{\tau,a_{\tau}}:a_{\tau},d_{\tau,a_{\tau}}\in
H_{\tau},t>\tau\geq t-w\\}$

2 while  _$T >t>w$_ do

3 $q_{\theta^{w}}$ $\leftarrow$ $\Sigma_{\theta}p(\theta)p(d|\theta)$

4 for  _$a_{k}\in W$_ do

5 $q_{\theta^{W},a}(d)$ $\leftarrow$ $\frac{|\\{d_{a_{k}}:d_{a_{k}}=d,d_{a}\in
W|d\\}|}{|\\{a_{k}:a_{k}\in W\\}|}$ $\forall d$

6

7 end for

8 $D^{w}(a)$ $\leftarrow$ $\Sigma_{d}q_{\theta^{w},a}(d)d/N$ $\forall a$

9 if  _$d_{t,a_{t}} >\Sigma_{\theta}\Sigma_{d}p(\theta)p(d|\theta,a_{t})d$_
then

10 $D^{w}(a_{k})$ $\leftarrow$ $max(D^{w}(a_{k}),D^{w}(a_{k-1}))$, $\forall k$

11 else

12 $D^{w}(a_{k})$ $\leftarrow$ $min(D^{w}(a_{k}),D^{w}(a_{k-1}))$, $\forall k$

13 end if

14 $q_{\theta^{w}_{a}}(d)$ $\leftarrow$ $binomial(d,N,D^{w}(a))$, $\forall
d,a$

15 end while

Algorithm 6 Transferability Test-Window Variant(w)

Information Structure In [Russo and Van Roy, 2018], they looked at how the
algorithm invests in indirect information when $\vec{g}$ is approximated by
$I(\theta;d)$ instead of $I(a^{*};d)$. In our setting, $a^{*}$ are geared with
with $\theta$, i.e. in universes where individuals are willing to pay more,
the optimal prices are also higher.Thus, the variant ACIDP-$\theta$ helps
reduce the uncertainty about $\theta$ and improve demand curve estimation,
which follows by the trivial solution of optimal price.

###  A.2 Other Policies

$\epsilon$-Greedy (EG) At each time t, the algorithm choose the price that
yields the highest empirical reward with $\epsilon$ $\in(0,1)$ and randomly
pick the other $k-1$ prices with $1-\epsilon$.

Upper Confidence Bound (UCB) UCB family are well-developed in bandit
literatures. UCB make optimistic decisions by selecting the price with the
highest reward upper bound $\bar{r_{a}}+c\sqrt{\log t/n(a_{k})}$ where
$n(a_{k})$ is the number of times $a_{k}$ is pulled and $c$ is a hyper-
parameter that motivates exploration. UCB-tuned substitutes c with
$min(\frac{1}{4},V)$. This tunable version takes the variance in outcomes into
account where $V=\frac{1}{n}\sum r(a)^{2}-\bar{r(a)^{2}}+\sqrt{2\log t/n}$.

UCBPI uses $argmax\ \bar{r_{a}}+a_{k}\sqrt{\log t/n(a_{k})}$ along with a
rule-based partial identification technique to filter out the obvious sub-
optimal prices initially. This version was built specifically for dynamic
pricing in stationary environments and empirically encourage exploration in
higher prices.

Thompson Sampling(TS) Thompson sampling choose according to the posterior
probability that each arm is perceived as the best
$p(a_{t}=a|H_{\tau})=p(a^{*}=a|H_{\tau})$ where $a^{*}=argmax\
\mathbb{E}(r(d)|\theta)$.

##  Appendix B Simulation

In this section we discuss the details and additional findings in our
simulation. Other parameters used in the simulation setting: $\epsilon=0.1$,
$r_{decay}=0.1$, $\alpha_{1}=0.05$, $\alpha_{2}=0.01$, $w=300$, $n=5$ in
sequence test. The performance are summarized in the following sections.

###  B.1 Case1: Stationary

In the stationary case, all candidates perform satisfactorily. To demonstrate
the impact of sample sizes on exploration, we utilize the ACIDP with
hyperparameters L=2, n=1, L=4, n=1, L=2, n=2. Both of the latter two cost 80
rounds at initialization, so their regret develops more steeply at the start
(see figure 5). They do, however, promptly detect the optimal arms and have
minimal regret for the remainder of the time. ACIDP-$\theta$, on the other
hand, performs relatively well in previous periods but suffers from an
insufficient investigation in a single trial.

Table 1: Case1 Result Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=2, n=1 | 100.5 | 56.4 | 238.5 | 53.3
| L=4, n=1 | 161.5 | 93.7 | 339.4 | 84.4
| L=2, n=2 | 182.6 | 89.9 | 393.5 | 78.1
ACIDP-$\theta$ | L=2, n=1 | 200.3 | 243.0 | 867.4 | 41.2
EG |  $\epsilon$=0.05 | 206.2 | 81.9 | 405.9 | 125.4
|  $\epsilon$=0.1 | 321.8 | 99.9 | 493.9 | 229.5
|  $\epsilon$=0.15 | 365.1 | 70.7 | 511.8 | 286.0
TS |  | 102.9 | 108.8 | 395.9 | 9.3
UCBPI |  | 278.9 | 26.4 | 319.3 | 230.8
UCB-Tuned |  | 124.5 | 19.1 | 160.9 | 95.9
UCB | c=1 | 165.7 | 8.5 | 182.1 | 153.5
| c=2 | 388.3 | 28.6 | 436.5 | 344.7
Figure 5: Regret and Price Selection (red line denotes $a^{*}$) in Case1:
Stationary.

###  B.2 Case2: Rapid Growth

In the case of rapid growth, policies are essential to achieve positive demand
growth. For all trials, UCB and TS maintain the convergent decision at the
$1000th$ round. Because their inertial decision and increased observation
causing them to consider the convergence price is extraordinary at
$1000^{th}$. Aside from ACIDP, EG is the only candidate that transfers to a
somewhat superior yet optimal arm on occasion. This is understandable since it
is less familiar with higher prices at $1000^{th}$, i.e. smaller sample sizes,
and so the empirical mean is easily inflated, leading to choice modifications.
In this case, ACIDP succeeded by detecting the change and inviting the
generator to mimic a bandit environment to transfer to.

Table 2: Case2 Result. Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=2, n=1 | 157.3 | 170.2 | 619.4 | 33.4
| L=4, n=1 | 167.5 | 91.5 | 406.7 | 91.0
| L=2, n=2 | 152.7 | 56.0 | 235.8 | 78.2
ACIDP-$\theta$ | L=2, n=1 | 135.0 | 107.2 | 379.0 | 50.9
EG |  $\epsilon$=0.05 | 546.7 | 305.1 | 1224.3 | 219.3
|  $\epsilon$=0.1 | 759.0 | 389.2 | 1379.8 | 381.4
|  $\epsilon$=0.15 | 929.9 | 311.4 | 1484.0 | 565.7
TS |  | 766.7 | 226.5 | 1164.1 | 479.3
UCBPI |  | 900.7 | 15.9 | 922.4 | 872.0
UCB-Tuned |  | 1138.7 | 193.7 | 1248.1 | 741.2
UCB | c=1 | 1299.4 | 354.6 | 1752.8 | 778.8
| c=2 | 1221.9 | 375.2 | 1894.8 | 576.3
Figure 6: Regret and Price Selection (red line denotes $a^{*}$) in Case2:
Rapid Growth.

###  B.3 Case3: Rapid Decline

In the case of rapid decline, candidates must implement price reductions in
order to receive bigger rewards. The maximum cumulative rewards at the
$2000^{th}$ round are the same as in the Rapid Growth case. Interestingly, TS,
UCB, and EG behave radically differently and result in higher total regret in
general. In contrast to the previous case, these policies lose faith in the
previously convergent conclusion and rush to figure out the new one. However,
due to prior experience, it takes more effort to investigate and identify the
ideal pricing in the new environment. ACIDP, on the other hand, went through
similar steps as the previous example and ended up with equivalent regret.

Table 3: Case3 Result. Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=2, n=1 | 194.7 | 120.9 | 399.0 | 53.2
| L=4, n=1 | 206.7 | 88.3 | 416.2 | 112.7
| L=2, n=2 | 171.8 | 42.1 | 228.8 | 94.3
ACIDP-$\theta$ | L=2, n=1 | 145.8 | 136.8 | 397.5 | 25.4
EG |  $\epsilon$=0.05 | 869.9 | 243.4 | 1406.4 | 613.6
|  $\epsilon$=0.1 | 890.5 | 91.0 | 1114.8 | 800.1
|  $\epsilon$=0.15 | 952.5 | 71.1 | 1060.9 | 831.2
TS |  | 1620.1 | 347.3 | 2096.2 | 953.7
UCBPI |  | 1775.8 | 623.5 | 2158.6 | 572.4
UCB-Tuned |  | 1106.4 | 540.0 | 1782.4 | 445.5
UCB | c=1 | 1255.2 | 559.0 | 1911.5 | 376.9
| c=2 | 742.8 | 26.5 | 793.5 | 708.2
Figure 7: Regret and Price Selection (red line denotes $a^{*}$) in Case3:
Rapid Decline.

###  B.4 Case4: Seasonality

In the case of seasonality, candidates need to overcome (1) continuous (2)
simultaneous up and down shifts and may receive a bonus if they notice the
recurrent change. In this case, UCB suffers from a combination of the two
modes of confusion mentioned above, while TS continues to exploit at the same
price. Because the observation is not identically distributed in each round,
it is more difficult for an agent to effectively recognize the genuine optimal
price in this case. However, in the later rounds, ACIDP can function optimally
and leverage the previous experience..

Table 4: Case4 Result. Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=2, n=1 | 203.2 | 113.6 | 422.3 | 87.8
| L=4, n=1 | 245.4 | 99.4 | 434.1 | 157.6
| L=2, n=2 | 231.0 | 63.5 | 317.4 | 124.1
ACIDP-$\theta$ | L=2, n=1 | 260.0 | 83.6 | 437.3 | 188.9
EG |  $\epsilon$=0.05 | 767.3 | 185.4 | 1217.3 | 553.2
|  $\epsilon$=0.1 | 761.4 | 149.2 | 1081.6 | 569.4
|  $\epsilon$=0.15 | 864.2 | 141.0 | 1149.0 | 686.5
TS |  | 481.5 | 23.1 | 500.1 | 424.3
UCBPI |  | 654.6 | 83.3 | 801.7 | 504.6
UCB-Tuned |  | 746.7 | 352.1 | 1449.5 | 408.2
UCB | c=1 | 580.0 | 110.0 | 787.8 | 439.9
| c=2 | 657.4 | 117.0 | 945.0 | 517.3
Figure 8: Regret and Price Selection (red line denotes $a^{*}$) in Case4:
Seasonality.

###  B.5 Case5: Volatility

In the volatility case, the fluctuation is assumed to be independent from one
period to another, observing the true optimal arm in the next round is
impossible. However, we show that regret can be reduced by adapting rapidly
enough and following the trend. We also discover that alternative candidates
may price differently across the horizon under comparable demand levels. This
is due to an inability to let go of past experiences, implying their
performance can be considerably improved by learning when to forget past
knowledge. The environmental diversity, on the other hand, is recorded as
parallel universes in ACIDP; hence, obsolete knowledge does not constrain
future decisions.

Table 5: Case5 Result. Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=2, n=1 | 127.5 | 25.8 | 164.8 | 93.1
| L=4, n=1 | 159.8 | 28.3 | 221.3 | 124.9
| L=2, n=2 | 150.4 | 30.3 | 190.8 | 100.5
ACIDP-$\theta$ | L=2, n=1 | 119.1 | 17.6 | 152.6 | 90.7
EG |  $\epsilon$=0.05 | 575.9 | 119.7 | 825.1 | 403.1
|  $\epsilon$0.1 | 596.3 | 119.7 | 885.8 | 460.0
|  $\epsilon$=0.15 | 637.0 | 105.5 | 827.6 | 511.7
TS |  | 532.1 | 163.8 | 729.2 | 328.4
UCBPI |  | 534.9 | 100.6 | 771.3 | 415.4
UCB-Tuned |  | 707.7 | 175.8 | 1080.2 | 336.5
UCB | c=1 | 611.1 | 179.4 | 779.3 | 344.7
| c=2 | 564.3 | 171.6 | 853.0 | 357.6
Figure 9: Regret and Price Selection (red line denotes $a^{*}$) in Case5:
Volatility.

###  B.6 Case6: Upside-Down

The Upside-Down case is intended to imitate dramatic environmental shifts, and
optimality can only be attained through a thorough exploration of the new
environment. We designed it to be similar to the second case, which is more
friendly to alternative policies, particularly EG. In this situation, while
ACIDP recognizes upward pricing adjustments without transferability, they
suffer from credibility degradation and do not completely transfer into the
new environment. The regular ACIDP processes through all three steps of
audition to achieve credibility, optimality, and transferability.

Table 6: Case6 Result. Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=2, n=1 | 509.0 | 503.0 | 1886.9 | 165.7
| L=4, n=1 | 554.2 | 511.9 | 1926.0 | 217.7
| L=2, n=2 | 365.7 | 126.1 | 629.7 | 221.5
ACIDP-$\theta$ | L=2, n=1 | 387.6 | 135.2 | 619.7 | 240.3
ACIDP | without transferability test | 1041.4 | 403.5 | 1911.0 | 597.0
ACIDP-w | window variant | 529.8 | 95.2 | 663.9 | 363.5
EG |  $\epsilon$=0.05 | 698.9 | 241.8 | 1000.6 | 309.8
|  $\epsilon$=0.1 | 693.5 | 215.0 | 1074.8 | 379.2
|  $\epsilon$=0.15 | 933.5 | 218.9 | 1275.2 | 482.1
TS |  | 1197.7 | 198.6 | 1423.4 | 964.0
UCBPI |  | 1318.8 | 73.8 | 1519.8 | 1263.1
UCB-Tuned |  | 1453.8 | 208.6 | 1864.5 | 1113.9
UCB | c=1 | 1489.3 | 307.1 | 1931.1 | 895.6
| c=2 | 1308.4 | 446.0 | 1679.4 | 292.6
Figure 10: Regret and Price Selection (red line denotes $a^{*}$) in Case6:
Upside-Down.

###  B.7 Real World Data

The Criteo Sponsored Search Conversion Log simulation is a real-life example
of the Upside-Down case. This time the $T$, $k$, and $N$ are scaled up to
cater to wider applications. Here we discussed several challenges identified
in this dataset. Firstly, each of the three products has a completely distinct
valuation and demand curve. The price needs to go up and down while the
underlying demand are completely unrelated. Second, the valuation distribution
cannot easily be approximated by common parametric families. This, however,
rendered ACIDP an even more powerful policy as it does not assume any shape on
valuation. Finally, conversion rates are typically low in the online
advertisement industry (ranging from 2% to 20% across products.) Therefore,
there are two critical factors affects N, number of clicks per round in this
context. 1. how fast an agent is allowed to make a new decision. 2. the sample
size needed in terms of demand utilized to update the decision. Because the
typical number of clicks each day for a single product is roughly 250, we set
N=500.

Table 7: Real Data: Criteo Experiment Result. Policy | Hyperparameters | Mean Regret | Standard Error | Max | Min
---|---|---|---|---|---
ACIDP | L=4, n=1 | 38915.97 | 15637.81 | 78699.4 | 26595.33
ACIDP-w | window variant | 26723.16 | 2115.70 | 29568.53 | 23473.74
EG |  $\epsilon$=0.05 | 83775.79 | 25410.65 | 127203.09 | 52124.14
|  $\epsilon$=0.1 | 106739.31 | 11245.25 | 120781.82 | 86027.40
|  $\epsilon$=0.15 | 133023.59 | 14774.32 | 158582.07 | 107559.25
TS |  | 199509.26 | 74.01 | 199622.38 | 199384.65
UCB-Tuned |  | 235209.70 | 88035.52 | 373923.95 | 132805.21
UCB | c=1 | 277109.95 | 139415.34 | 434026.10 | 107524.25
| c=2 | 191249.57 | 101755.70 | 429739.28 | 107482.55
Figure 11: Regret and Price Selection (red line denotes $a^{*}$) in Real World
Data.

##  Appendix C Visualization of Experiment Details

Implementation of Algorithm3 Here we visualize the generator process in case6.
The blue generated distribution is associated with $\theta^{C}$. It helps
enhance credibility by approaching the true distribution. And in the estimated
demand and profit curve, we show that ACIDP is capable of optimize price
choice with limited and incomplete observation in both stages.

Figure 12: The counterfactual universe constructed before(above) and
after(below) market shift in case 6. (a) discrete valuation derived from
demand (b) decorated with noise (c) associated demand curve (d) associated
profit curve

Demand curve of the three products in Criteo Data The three chosen products A,
B, C are originally indexed B442064C9D31A52BCAE0D18212FCFA1E,
0CAD35A37452D99F0BE65C9299EBF729, and 917676DCA7640B0256200468FB76B7BD in the
dataset. Their demand curve is summarized as below. Their visualization in
line plots (see 13) showcase how destructive real-life non-stationarity could
be.

Table 8: True Demand $D_{a_{t}}$ Calculated From The Criteo Dataset Price | Product A | Product B | Product C |  | Price | Product A | Product B | Product C
---|---|---|---|---|---|---|---|---
10 | 1 | 1 | 1 |  | 260 | 0.101 | 0.32 | 0.373
20 | 0.998 | 1 | 0.921 |  | 270 | 0.093 | 0.309 | 0.368
30 | 0.978 | 0.991 | 0.85 |  | 280 | 0.09 | 0.229 | 0.357
40 | 0.963 | 0.982 | 0.796 |  | 290 | 0.088 | 0.201 | 0.325
50 | 0.945 | 0.976 | 0.743 |  | 300 | 0.084 | 0.183 | 0.312
60 | 0.921 | 0.956 | 0.687 |  | 310 | 0.081 | 0.172 | 0.276
70 | 0.87 | 0.94 | 0.658 |  | 320 | 0.079 | 0.146 | 0.232
80 | 0.674 | 0.879 | 0.618 |  | 330 | 0.07 | 0.132 | 0.2
90 | 0.474 | 0.846 | 0.593 |  | 340 | 0.066 | 0.124 | 0.168
100 | 0.401 | 0.821 | 0.567 |  | 350 | 0.062 | 0.117 | 0.149
110 | 0.348 | 0.786 | 0.553 |  | 360 | 0.055 | 0.113 | 0.13
120 | 0.308 | 0.781 | 0.534 |  | 370 | 0.055 | 0.11 | 0.119
130 | 0.28 | 0.764 | 0.519 |  | 380 | 0.051 | 0.101 | 0.104
140 | 0.264 | 0.753 | 0.499 |  | 390 | 0.051 | 0.095 | 0.091
150 | 0.233 | 0.737 | 0.482 |  | 400 | 0.051 | 0.084 | 0.08
160 | 0.207 | 0.625 | 0.469 |  | 410 | 0.048 | 0.077 | 0.071
170 | 0.183 | 0.505 | 0.453 |  | 420 | 0.042 | 0.075 | 0.064
180 | 0.163 | 0.499 | 0.443 |  | 430 | 0.04 | 0.069 | 0.056
190 | 0.154 | 0.492 | 0.433 |  | 440 | 0.035 | 0.066 | 0.053
200 | 0.137 | 0.486 | 0.426 |  | 450 | 0.035 | 0.062 | 0.048
210 | 0.119 | 0.397 | 0.421 |  | 460 | 0.035 | 0.055 | 0.048
220 | 0.115 | 0.388 | 0.409 |  | 470 | 0.035 | 0.051 | 0.045
230 | 0.11 | 0.358 | 0.405 |  | 480 | 0.026 | 0.049 | 0.043
240 | 0.11 | 0.338 | 0.398 |  | 490 | 0.022 | 0.049 | 0.04
250 | 0.104 | 0.329 | 0.393 |  | 500 | 0.022 | 0.049 | 0.037
Figure 13: Normalized Demand (Blue) and Revenue (Orange) Curve of Product A,
B, C.