Online learning for two-sided sequential transport matchingmarkets with temporal effects
A. Giudicia,∗ , J. van Dalena , T. Lub and R. Zuidwijkaa Rotterdam School of Management, Rotterdam, The Netherlands

giudici@rsm.nl, jdalen@rsm.nl, rzuidwijk@rsm.nlb School of Business, University of Connecticut, Storrs, Connecticut

tao.lu@uconn.edu∗ Corresponding author

Extended abstract submitted for presentation at the 11th Triennial Symposium on
Transportation Analysis conference (TRISTAN XI)
June 19-25, 2022, Mauritius Island

January 15, 2022
Keywords: two-sided platform, inland transport, spot-market, multi-armed bandits

1Introduction

Two-sided digital platforms are ubiquitous in many industries. In many notable cases, theseonline markets have been disrupting industries; examples are ride-hailing platforms or home-stayplatforms. In logistics, several platform initiatives have been taken, and despite the expecteddisruptive potential, these platforms have not been disrupting the industry yet. We consider thecase of a two-sided digital marketplace for spot transport, where shippers - the companies in needof transport for available cargo - search for carriers - transport companies - that can transport
their goods. In our case, we consider the inland waterway transport market where bulk goods
are loaded onto and transported by river vessels (barges). Motivated by our collaboration witha digital transport company, we take the perspective of the company that operates such a twosided platform where shippers and carriers match to execute transport. Transport requests arechiefly characterized by temporal, spatial, and commodity-related features. On the marketplace,decentralized matching decisions take place between the two sides: carriers screen transport
requests and place offers, which are then evaluated by the shippers. When an offer is acceptedby a shipper, a match is formed and the platform owner earns a revenue. After matching, agentsmight return to the marketplace to post or execute new requests, partially depending on theexperienced service.
The platform owner manages how the stream of transport requests generated by the shippers
is presented to each carrier. In other words, the platform owner decides what assortment oftransport requests will each carrier choose from. As multiple carriers might signal their interest
to the same shipper, the shipper will choose a single carrier between an induced assortment ofinterested ones. As two assortments are created in a sequence, our problem is similar to thetwo-sided sequential assortment problem of Ashlagi et al. (2019). The choices of either side aredetermined by the preferences of the individual users who rationally chose between the presentedalternatives.
In this problem setting, information is scarce, partially available, and of transactional nature.
The platform possesses only beliefs on users’ characteristics, preferences, behavior, etc., whichneeds to be actively learned. A traditional approach of estimating beliefs once and then deciding
on the optimal assortment is not practical in our setting where information is accumulated
TRISTAN XI Symposium

Original abstract submittal

A. Giudici, J. van Dalen, T. Lu and R. Zuidwijk

2over time and past choices affect the exogenous information process. The platform owner has
the opportunity to actively learn users’ characteristics by experimenting with the assortment
generated. This general problem has been formalized by the multi-armed bandit models which
we adopt for our setting.

2Methodology

Our model is largely inspired by multi-armed bandits, which has been a flourishing concept inrecent years (Lattimore and Szepesvári, 2019). Essentially, a multi-armed bandit model captures
the setting where a decision-maker aims at maximizing a reward over a time horizon T ={0, . . . , T } (T ∈ N>0 ) while learning to choose between alternative actions a ∈ A of unknown
reward distribution. As the action is taken, the environment responds with a, possibly stochastic,
reward which provides information on the reward distribution for that action.
In our setting, an action corresponds to choosing what assortment of transport requests eachcarrier will evaluate. The reward at time t for an assortment at , i.e., the expected number ofmatches QtHt (at ), depends on the observed history Ht of information accumulated from pastevaluations of the carriers and shippers up until time t.
The performance of P
an algorithm for multi-armed
bandits is evaluated by computing thecumulative regret RT := Tt=0 Q̂t (a∗ ) − QtHt (at ) between the expected reward Q̂t (a∗ ) obtained
when knowing the true reward distribution (a∗ := arg maxa∈A Q̂t (a)) and the history-dependent
reward QtHt (at ).
We solve the problem of finding a suitable approach to minimize the bandit regret in adata-driven setting by adapting the upper confidence bound approach to our case (Sutton andBarto, 2018, Agrawal et al., 2019a). The underlying idea is that of moderating action choiceby both considering an estimated value of the reward and an upper bound on its performance.
Because our industry partner needs to manage a large volume of requests quickly, we computethe next action rapidly by developing a tailored reduction of the objective value and a simulated
annealing heuristic to maximize the upper confidence bound. Simulated annealing is a wellestablished random meta-heuristic framework where the solution space is explored by accepting
both improved and worsened solutions with a certain probability (van Laarhoven and Aarts,
1987, Bertsimas and Tsitsiklis, 1993). An overview of the algorithm we implement is given in
Algorithm 1 where the upper confidence bound UCBt (a) is defined up to a given confidence
parameter c ∈ R, as followssln(t)tt tUCB (a) := Q (a ) + c(1)Nt (a)
where Nt (a) counts the number of times an action has been taken and, therefore, provides ameasure of the confidence of our estimates. Note that if Nt (a) = 0, then a is considered amaximizing action. The idea of the upper confidence bound selection is that the square root
term is a measure of the uncertainty related to a certain action. Indeed, the more a given action
has been taken, the more confident our estimates of the expected number of deals are. If instead,a certain action has never been taken, then our estimate of Qt is poor and should not be trusted.
The confidence parameter c tunes the choice of the next action between the beliefs or the measureof confidence.

3Results

We test the performance of our bandit algorithm through simulations. For brevity, we report
only the main result. In our experiments, we consider the case where a set I of 5 carriers interact
with a set J of 5 shippers for T = 300 epochs. Carriers and shippers are characterized each
TRISTAN XI Symposium

Original abstract submittal

A. Giudici, J. van Dalen, T. Lu and R. Zuidwijk

3

RT (π)/TcT

Figure 1 – Performance of our methodby a randomly chosen 3-dimensional vector xi ∈ [0, 1]3 and yj ∈ [0, 1]3 (for i ∈ I and j ∈ J),
respectively. Transport requests are characterized by randomly generated vectors ztj ∈ R5 .
Choices are made following a multinomial choice model as typical in the assortment optimization
literature (van Ryzin and Mahajan, 1999). Characteristics of users and transport requests affecttheir individual choices, i.e., the chance that a carrier reacts to a transport request among theassorted ones as well as the chance of a shipper accepting a carrier among the ones that reacted
to the transport requests.
We evaluate the performance of our approach by computing the cumulative regret between the
expected optimal decision a∗ and the realized number of deals by the choice of the action. Given
our parameters, we execute the same simulation 100 times to compute reliable estimates of theexpected performance and present our results for different values of the confidence parameter c(cf. Eq. (1)).
We show in Figure 1 the ratio between the cumulative regret and the time horizon T , together
with a 95% confidence band around it. We observe that, with minimal long-term dependency
on the confidence parameter c, we obtain a limiting constant regret increase. Our result is inline with that of the model in Sauré and Zeevi (2013) where an asymptotically-constant regret isfound in the application of their model on realistic data in Agrawal et al. (2019b). As in our case,
Sauré and Zeevi (2013) achieves a constant cumulative regret because of the complex learning
task where almost two thousand different items are considered. For us, instead, the complexityof the learning task is due to the exponential number of dual-sided combinations.

Algorithm 1 Multi-armed bandit algorithm overview
1: Initialize all parameters
2: for t = 1, . . . , T do
3:update all beliefs using the history Ht
4:
update the assortment menu maintaining only open cargo offers
5:take an action a′ that maximizes the upper confidence bound UCBt (a) using the simulated
annealing heuristic
6:
update the history Ht
7: end for
TRISTAN XI Symposium

Original abstract submittal

A. Giudici, J. van Dalen, T. Lu and R. Zuidwijk

44Conclusion

Our work provides a three-fold contribution to the literature. First, we propose a dynamic modelof matching and learning for dual-sided digital transport marketplaces. Second, we enrich theassortment optimization model by capturing the timing of user logins and expiring shipments.
Third, we achieve performances of dynamic assortment optimization models whilst capturing
more complex dynamics.
Learning while matching in dual-sided digital transport marketplaces. To the bestof our knowledge, we are the first to consider two-sided assortment optimization in the transport
spot market. The main characteristic of this market is the inherent time pressure resulting
from transport deadlines. We provide an algorithm that combines learning and exploration indual-sided assortment optimization for real two-sided online marketplaces.
Stochastic evaluations on expiring assortments. Because the evaluation of an assortment requires carriers to log in while shipments expire over time, we include in our model theeffect of uncertain carrier log-in and shipment deadlines. This means that beliefs on the next
user login and shipment deadline affect the assortment decision.
Computational experiments. Our algorithm and model have been tested on a simulated
online marketplace we constructed for testing purposes. We show that our method achieves
asymptotic performances comparable to that of traditional, i.e., not two-sided, dynamic assortment optimization models with learning when exposed to similar learning challenges (Sauré andZeevi, 2013).
Future research can expand this work in different directions by considering enriched solution
methods or modeled features. For instance, we focus on the development of a single strategy that
does not consider temporal changes of user behavior (e.g., due to market trends). Moreover, we
do not consider the opportunity for optimizing matches from the transport point of view. Bothdirections could be part of future research.

5References

References
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. (2019a). MNL-bandit: A dynamic learning
approach to assortment selection. Operations Research, 67(5):1453–1485.
Agrawal, S., Avadhanula, V., Goyal, V., and Zeevi, A. (2019b). MNL-Bandit: A Dynamic Learning
Approach to Assortment Selection. Operations Research, 67(5):1453–1485.
Ashlagi, I., Krishnaswamy, A. K., Makhijani, R., Saban, D., and Shiragur, K. (2019). Assortment
planning for two-sided sequential matching markets. arXiv.
Bertsimas, D. and Tsitsiklis, J. (1993). Simulated Annealing. https://doi.org/10.1214/ss/1177011077,
8(1):10–15.
Lattimore, T. and Szepesvári, C. (2019). Bandit Algorithms. Technical report.
Sauré, D. and Zeevi, A. (2013). Optimal Dynamic Assortment Planning with Demand Learning. Manufacturing & Service Operations Management, 15(3):387–404.
Sutton, R. and Barto, A. (2018). Reinforcement learning: An introduction.
van Laarhoven, P. J. M. and Aarts, E. H. L. (1987). Simulated annealing. In Simulated Annealing:
Theory and Applications, pages 7–15. Springer Netherlands, Dordrecht.
van Ryzin, G. and Mahajan, S. (1999). On the Relationship Between Inventory Costs and Variety Benefits
in Retail Assortments. Management Science, 45(11):1496–1509.

TRISTAN XI Symposium

Original abstract submittal