# Craftium: An Extensible Framework for Creating Reinforcement Learning
Environments

Mikel Malagón
University of the Basque Country UPV/EHU
Donostia-San Sebastián, Spain
<EMAIL_ADDRESS>
Josu Ceberio
University of the Basque Country UPV/EHU
Donostia-San Sebastián, Spain
<EMAIL_ADDRESS>
Jose A. Lozano
University of the Basque Country UPV/EHU
Basque Center for Applied Mathematics (BCAM)
Donostia-San Sebastián, Spain
<EMAIL_ADDRESS>

###### Abstract

Most Reinforcement Learning (RL) environments are created by adapting existing
physics simulators or video games. However, they usually lack the flexibility
required for analyzing specific characteristics of RL methods often relevant
to research. This paper presents Craftium, a novel framework for exploring and
creating rich 3D visual RL environments that builds upon the Minetest game
engine and the popular Gymnasium API. Minetest is built to be extended and can
be used to easily create voxel-based 3D environments (often similar to
Minecraft), while Gymnasium offers a simple and common interface for RL
research. Craftium provides a platform that allows practitioners to create
fully customized environments to suit their specific research requirements,
ranging from simple visual tasks to infinite and procedurally generated
worlds. We also provide five ready-to-use environments for benchmarking and as
examples of how to develop new ones. The code and documentation are available
at https://github.com/mikelma/craftium/.

Figure 1: Images of games based on the Minetest game engine and the
environments distributed with the Craftium package.

##  1 Introduction

Reinforcement Learning (RL) research is inherently tied to the environments
where agents are trained, tested, and analyzed. Each new insight or
advancement in RL is supported by an environment that enables specific
behaviors to emerge and be studied. However, many environments extensively
employed in the RL literature are physics simulators or video games, not
particularly developed for RL research, and have been adapted to suit general
RL requirements. These environments include the Arcade Learning Environment
[5, 16] based on Atari video games, DeepMind Lab environments [4] that were
based on Quake III Arena, theNetHack Learning Environment [15] based on the
original NetHack game, and MineRL [12] and MineDojo [10] based on the original
Minecraft game. These environments or benchmarks offer a limited number of
predefined tasks, with minimal options for practitioners to modify the game’s
behavior for specific research needs. Customization is typically restricted to
adjusting the parameters of predefined tasks, usually lacking support for
creating new environments. Furthermore, many RL tasks only require a minimal
subset of a game, but game-based environments often need to simulate the
entire video game. This leads to significant computational overhead, adding to
the already demanding computational requirements of training RL agents.

Although some environment creation frameworks exist [2, 20, 7], they fall
short compared to the rich and complex 3D visual tasks provided by MineRL,
DeepMind Lab, or CARLA [12, 4, 9]. Despite their suitability for rapid
experimentation, visually simple and 2D games greatly differ from real-world
tasks often interesting for RL and robotics research. In fact, current
research in RL and embodied agents is investing significant effort to develop
methods that operate in complex 3D environments [18, 3, 1]. However, the RL
practitioner is faced with the choice between a customizable environment
framework limited to visually simple tasks or a complex 3D environment that
depends on a computationally demanding video game (possibly close-sourced, as
is the case for Minecraft) with minimal or no option for task customization.

In this paper, we present Craftium, a 3D visual environment creation framework
thought to be extended and customized for RL research. Craftium (see Figure 1)
is based on the open-source Minetest game engine111Project’s main page:
https://www.minetest.net/., intended to create voxel-based games. Minetest is
implemented in C++, while it exposes a Lua API222API documentation at
https://api.minetest.net/., a scripting programming language focused on
simplicity and performance333Lua’s main page: https://lua.org/., allowing the
complete customization of the game engine. In fact, Minetest’s community has
implemented many games and modifications444Most of these are published in
ContentDB: https://content.minetest.net/. (referred to as mods) using this
API, ranging from chess games to infinite and procedurally generated worlds
with varied fauna. Its rich extensibility via its Lua API, the efficient C++
implementation, and the availability of many existing games and mods make
Minetest the ideal platform for creating RL environments. Consequently,
creating new environments only requires creating a Minetest world (which can
be as simple as a few clicks, created via Lua script, or by playing the game)
and implementing the Lua script that defines the reward and termination
mechanics. To make this possible, Craftium makes minimal modifications to the
original Minetest source code, maintaining compatibility with future updates
to the game engine. Moreover, Craftium provides an easy-to-use and fully
documented Python library that the user can employ to load, modify, create,
and interact with the environments. Furthermore, Craftium implements the
popular Gymnasium interface, the modern standard for RL research, making it
compatible with many other libraries and projects as [19, 13, 21]. Finally,
although Craftium is not a package of environments per se, we provide five
predefined environments as benchmarks and serve as examples of how to create
new ones. We also provide examples and ready-to-use implementations to train
RL agents in Craftium environments.

In summary, this paper introduces Craftium, a novel, intuitive, documented,
and highly flexible platform for developing rich and visual 3D environments.

##  2 Background: Minetest and Minecraft

Minecraft is a sandbox game555Sandbox games allow players extensive creative
freedom to explore, build, and manipulate the game environment with few
constraints or predetermined goals. where players explore a voxel-based,
procedurally generated 3D world, gather resources, craft tools, and construct
structures. Although Minecraft supports mods, it is limited by being a closed-
source game restricting access to its underlying logic. Additionally, its Java
implementation is known to impact the game’s performance.

In contrast, Minetest is an open-source voxel-based game engine inspired by
Minecraft, serving as a platform for creating games rather than being a game
itself. Minetest is implemented in the C++ programming language, known for its
high efficiency. Furthermore, Minetest exposes an extensive API in Lua, a
well-known embeddable scripting programming language focused on simplicity and
performance. Through its Lua API, Minetest enables extensive customization of
its behavior, facilitating creating, modifying, and extending games. Minetest
also provides a default game, Minetest Game666See
https://content.minetest.net/packages/Minetest/minetest_game/., that serves as
a stable and light-weight basis for mods and new games. However, many other
community-driven games exist in Minetest, such as VoxeLibre777See
https://content.minetest.net/packages/Wuzzy/mineclone2/. that offers more
similarities to the original Minecraft game, or drastically different games as
The Unexpected Gambit888See
https://content.minetest.net/packages/NO11/the_unexpected_gambit/. that
implements a chess game.

Figure 2: Interactions between the parts that involve training an RL agent
within the presented framework.

##  3 The Craftium framework

Training an agent in Craftium involves three main components, illustrated in
Figure 2. The first is the modified version of the Minetest game engine. The
main modifications include the ability to communicate with the Craftium
process (via the TCP protocol) and extensions to the Lua API for defining RL
tasks. We have kept changes to the original Minetest source minimal and non-
intrusive to ensure compatibility with future updates to the game engine. The
second component is Craftium, whose Python library facilitates communication
with Minetest and integrates with the popular Gymnasium API. The final
component is the agent, that employs the mentioned API to interact with the
environment.

The Craftium framework and the set of predefined environments that it includes
are detailed in the following lines.

Figure 3: Example of a 64x64 pixel RGB image observation in a Craftium
environment.

###  3.1 Observations, actions, and rewards

#### Observations.

In Craftium, observations are, by default, single RGB images of the player’s
main camera whose size can be customized (defined when instantiating the
environment). An example of such observation is provided in Figure 3. As
Craftium implements the Gymnasium API, the observation space of a task can be
further customized employing observation wrappers999See
https://gymnasium.farama.org/api/wrappers/observation_wrappers/. For instance,
the `FrameStack` wrapper stacks multiple consecutive images into a single
observation, allowing the agent to perceive movement only from observations.
Moreover, custom observation wrappers can also be created to further control
the space of observations.

#### Actions.

By default, actions are composed of 21 keyboard actions and a tuple that
defines the movement of the mouse (or camera). Keyboard-related actions are
binary variables with a value of 1 if the key is pressed and 0 otherwise. The
movement of the mouse is defined with the tuple
$(\Delta_{x},\Delta_{y})\in[-1,1]^{2}$, where $\Delta_{x}<0$ moves the mouse
to the left in the horizontal axis and $\Delta_{x}>0$ to the right, similarly,
$\Delta_{y}<0$ moves the mouse downwards in the vertical axis and
$\Delta_{y}>0$ moves it upwards. Thus, if $\Delta_{x}=\Delta_{y}=0$, the mouse
is not moved. Note that in Minetest games, mouse movement is mainly used to
move the player’s camera.

The default action space is designed to provide almost complete control of the
game to the player,101010Some controls like pausing the game or opening the
chat have been excluded. providing great flexibility to define complex tasks.
Craftium also provides two action wrappers111111The wrappers are:
BinaryActionWrapper and DiscreteActionWrapper. that can be used to customize
the action space for problems that do not require the whole default space,
simplifying the task for the learning agent. These wrappers allow defining
alternative action spaces, where actions are indices or binary vectors, that
only consider a subset of the 21 key actions and discretized actions for the
mouse movement.121212Discretized mouse movements are: move the mouse to the
left, right, upwards, and downwards. The magnitude of the movements can be
defined by the user.

#### Rewards.

Craftium modifies Minetest to include Lua functions to get and set the reward
value. The latter enables implementing reward functions inside Minetest mods,
opening the door to the vast possibilities that Minetest’s Lua API offers. An
example of such a mod is discussed in Section 3.2.

###  3.2 Creating custom environments

⬇

name = craftium_mod

description = Craftium mod.

depends = default

Figure 4: Example configuration file for a mod implementing the custom
Craftium environment. Note that the mod depends on the default mod, available
in Minetest’s default game, providing basic functionalities.

⬇

minetest.register_on_dignode(function(_pos, node)

if string.find(node["name"], "tree") then

set_reward_once(1.0, 0.0)

end

end)

\parminetest.register_on_dieplayer(function(_obj, _rsn)

set_termination()

end)

Figure 5: Simple Lua script implementing the mechanics of a custom
environment.

Craftium environments have two main components: the world and the mod. The
first step when creating a custom Craftium environment is to generate the
world the agent will interact with. Although Minetest offers unlimited
possibilities, creating a world can be as simple as a few clicks when using an
already predefined map generator or mod.131313Map generators included with
Minetest can be found at https://wiki.minetest.net/Map_generator. If a finer
control over this step is needed, Minetest offers tools for this
purpose,141414Check https://github.com/minetest/minetestmapper. or custom Lua
mods can be used. Once the world is created, a Lua mod is used to control the
mechanics of the environment and define the reward. 151515Explaining how to
create Minetest mods is out of the scope of this paper, as excellent resources
already exist: https://rubenwardy.com/minetest_modding_book/en/index.html.

A mod is a directory with (at least) two files: a configuration file named
`mod.conf`, and a Lua script named `init.lua`. The configuration file is used
for the mod’s metadata, including the name, description, dependencies to other
mods, etc. An example of a typical mod configuration file is provided in
Figure 5. More interestingly, the `init.lua` file defines the task (e.g., the
reward function, termination conditions, player’s initial position). This file
is a Lua script that can use all the default functionalities that the Lua
programming language provides together with the ones provided by the
Minetest’s API. An example script for an environment where the objective is to
chop trees is illustrated in Figure 5. The first line registers a callback
function called every time the player (i.e., the agent) digs a node. This
function, checks if the dug node is part of a tree (line 2), and if that is
the case, sets the reward to 1 for that timestep (line 3). Note that
`set_reward_once` only sets the reward (function’s first parameter) from one
timestep, after resetting it to 0 (function’s second parameter). Finally, in
line 7 another callback is registered, calling a function that terminates the
episode (line 8) every time the agent’s health is exhausted (i.e., the player
dies).

Simple mods such as the one considered in this example can already be used to
generate a vast number of tasks and environments. Nonetheless, more complex
scripts and community-made games or mods can be integrated into Craftium
environments to further increase the available possibilities. See Section 3.4
for more examples of Craftium environments.

###  3.3 Interface

Craftium implements the popular Gymnasium API, a common and easy-to-use
interface for RL. The latter makes Craftium environments compatible with a
great variety of existing tools and projects to train, test, develop, and
analyze many RL algorithms. Some of these projects include: `stable-
baselines3` [19], Ray RLlib [17], CleanRL [13], and `skrl` [21]. Figure 6
shows an example that uses the mentioned interface. First, line 1 loads a
predefined Craftium environment (these are discussed later in Section 3.4),
then line 6 initiates an episode, obtaining the current observation and an
information dictionary. Note that the dictionaries can be used by Gymnasium to
provide additional information to the reward and termination and truncation
flags, elapsed time, or episodic return for example. Lines 7-12 implement the
agent-environment interaction loop, where a random action is selected (line 8)
and executed in the environment (line 9), returning the next observation, the
reward, and two boolean flags indicating whether the episode is terminated or
truncated, and the new information dictionary, respectively. In case the
episode is terminated or truncated (line 11), a new episode is initiated by
calling `env.reset` (line 12). Finally, once the main loop ends, the
environment is cleanly closed in the last line.

⬇

import gymnasium as gym

import craftium

\parenv = gym.make("Craftium/Room-v0")

\parobs, inf = env.reset()

for t in range(500):

a = env.action_space.sample()

obs, r, tm, tc, inf = env.step(a)

\parif tm or tc:

obs, inf = env.reset()

\parenv.close()

Figure 6: Example usage of the Gymnasium API with Craftium implementing a
randomly acting agent.

###  3.4 Provided environments

(a) Chop Tree

(b) Room

(c) Small Room

(d) Speleo

(e) Spiders Attack

Figure 7: Example observations from each of the predefined environments that
Craftium provides.

Although Craftium is primarily designed for creating new environments, it also
offers a set of baseline environments intended to serve as benchmarks and
examples for implementing environments of varying complexity.

By default, all the environments in this section share the same observation
space of RGB images $64\times 64$ pixels. Nonetheless, this parameter can be
modified when loading the environments. Regarding the action space, we use
action wrappers to simplify the default action space to only consider the
relevant actions for each task. Specifically, all environments employ discrete
actions $a\in\\{0,1,2,\ldots\\}$, where $a=0$ is the `NOP` action (no-op
action) and rest of the actions are different and are set according to the
requirements of the task. Below, we list and describe all the predefined
environments provided by Craftium, which are illustrated in Figure 7.

#### Chop tree.

The player spawns in a dense forest with many trees, equipped with a steel
axe. Every time the player chops a tree, a positive reward of 1 is given, and
0 otherwise. Available actions are: move forward, dig (used to chop), and move
the mouse left, right, up, and down. The maximum number of timesteps is set to
500, after which the episode is truncated.

#### Room, and small room.

The player is placed in one half of a closed room, and in the other half of
the room, a red block is spawned. The objective is to reach the red block as
fast as possible. At every timestep, the reward is set to -1 and when the
player reaches the block the episode terminates. The positions of the player
and the red block are randomized and changed in every episode, thus the agent
cannot memorize the position of the target. Available actions are: move
forward, move mouse left, and move mouse right. This environment has two
variants: room, which uses a large room made of diamond blocks; and small
room, with a considerably smaller room, facilitating reaching the target. The
timestep budget is smaller in the case of the smaller room variant, 200
timesteps, compared to the 500 timesteps in the larger room.

#### Speleo.

In this environment, the player spawns in a closed cave illuminated with
torches. The task is to reach the bottom of the cave as fast as possible. For
this purpose, the reward at each timestep is the negative position of the
player in the Y axis. Thus the reward gets more positive as the player goes
deeper into the cave. Six actions are available: move forward, jump, and move
the mouse left, right, up, and down. The episode is truncated after 500
timesteps.

#### Spiders attack.

The player is spawned in a closed cage with a spider inside it. The player is
equipped with a steel sword and the objective is to kill as many spiders as
possible until the end of the episode. Every time the player kills a spider,
the reward of that timestep is set to 1 and 0 otherwise. When all spiders
inside the cage are dead, spiders are respawned, adding one more spider to the
previous round. The episode terminates if the player’s health is exhausted,
survives until the end of the last round (with 5 spiders), or if episode
truncation is reached after 2000 timesteps. The actions are: move forward,
move left, move right, jump, attack, and move mouse left, right, up, and down.

##  4 Related work

The RL literature has proposed a vast number of environments and tasks to
train and benchmark algorithms, most of which are based on video games [5, 4,
23, 12, 15] or physic simulators [22, 11, 6]. Usually, environments offer
static scenarios with a limited number of adjustable parameters to adjust the
task to the particular needs of the researcher [5, 16]. However, these often
tend to be very limited and fail to reach the flexibility required in
research.

To overcome this issue, ProcGen [8] introduced procedurally generated 2D
environments. Nonetheless, the diversity of the environments is limited, and
modifications to existing environments are accomplished by changing predefined
parameters. Equivalently, the NetHack Learning Environment [15] also leverages
procedural generation in 2D environments, although environment customization
is similarly limited.

To further improve the customization of existing environments and the
flexibility when creating new ones, some works introduce Domain Specific
Languages (DSLs) for this purpose. For example, VizDoom [23] employs the
ZScript, the DSL of ZDoom (the game on which VizDoom is based), and MiniHack
[20] uses the `des-file format` inherited from the original NetHack game.
However, in many cases, DSLs are very specific to the purpose they were
created for and fail to provide the flexibility and expected features of
proper programming languages. For instance, the `des-file format` is
specifically designed for composing NetHack levels, but it is not a
programming language per se. Moreover, DSLs tend to deviate from the syntax
and semantics of mainstream programming languages, hindering their usage and
adoption.

Other works offer similar customization capabilities by allowing modifying and
creating new environments from the programming language they are implemented
in, usually Python, avoiding the mentioned issues of DSLs. For instance,
Griddly [2] and MiniGrid [7] offer a Python API for 2D grid-like environment
creation. While grid environments are fast to simulate, they often lack the
complexity and richness of others (e.g., procedural generation, weather
systems, animals, monsters, multiple biomes). In principle, more complex tasks
could be implemented in these frameworks. However, this would require
significant effort from researchers. Regarding 3D environments, MiniWorld [7]
offers a similar API to MiniGrid’s, also suffering from the same issues for
creating complex environments.

For visually complex and rich environments, Malmo [14] and MineRL [12] wrap
the popular Minecraft game in an easy-to-use Python library for RL.
Nevertheless, task customization and the creation of new environments are not
supported. More recently, MineDojo [10] has greatly improved the customization
capabilities of Minecraft-based environments. However, MineDojo limits
customization to the parameters of several predefined tasks, not allowing to
change the environment’s map (the world), for instance. Furthermore, the fact
that MineDojo is bound to Minecraft presents some additional constraints. On
the one hand, Minecraft is close sourced, which limits the customization
capabilities and, on the other, Minecraft is implemented in Java, a
programming language known to have significantly lower performance compared to
other programming languages such as C or C++.

##  5 Conclusion

Creating new environments or customizing existing ones is fundamental for the
progress of the RL field, especially in research, where specific
characteristics or behaviors of the methods are to be analyzed. However, many
of the existing environments and benchmarks in the RL literature offer very
limited or no customization capabilities at all [5, 16, 14, 12, 8, 10]. In the
light of this issue, some works have created libraries and platforms for
developing RL environments [2, 23, 7, 20], but depend on limited DSLs or only
offer grid-like 2D worlds.

In this work, we present Craftium, a rich and easy-to-use environment creation
framework based on the open-source Minetest voxel game engine. Minetest is
implemented in the C++ programming language, leveraging the efficiency of low-
level programming languages. Additionally, Minetest supports extensive
customization through its Lua API, allowing users to integrate their
modifications within the game engine with ease. These features make Minetest
the ideal platform for RL research. Specifically, Craftium makes minimal
modifications to Minetest to communicate with a tailored Python library.
Furthermore, Craftium implements the popular Gymnasium API, making it
compatible with a great number of existing tools and libraries [17, 13, 21,
19]. Craftium is completely open source and provides thorough documentation of
its Python library, while including five predefined tasks as examples and for
benchmarking purposes. The project is available at
https://github.com/mikelma/craftium/.

Although Craftium is an environment creation framework, we believe that future
work on creating additional environments is relevant, ultimately creating a
benchmark for comparing novel and baseline RL methods. As the Gymnasium API in
the case of the single agent setting, we think that multi-agent interactions
could be integrated into the proposed framework in the future, implementing
the Petting Zoo API161616See https://pettingzoo.farama.org/index.html. in this
case.

## Acknowledgements

We are grateful to Jose A. Pascual for the technical support and to Ainhize
Barrainkua for reading the preliminary versions of the paper.

Mikel Malagón acknowledges a predoctoral grant from the Spanish MICIU/AEI with
code PREP2022-000309, associated with the research project
PID2022-137442NB-I00 funded by the Spanish MICIU/AEI/10.13039/501100011033 and
FEDER, EU.

This work is also funded through the BCAM Severo Ochoa accreditation
CEX2021-001142-S/MICIN/AEI/10.13039/501100011033; and the Research Groups
2022-2025 (IT1504-22), and Elkartek (KK-2021/00065 and KK-2022/00106) from the
Basque Government.

## References

  * Abi Raad et al. [2024] M. Abi Raad, A. Ahuja, C. Barros, F. Besse, A. Bolt, A. Bolton, B. Brownfield, G. Buttimore, M. Cant, S. Chakera, et al.  Scaling instructable agents across many simulated worlds.  _arXiv preprint arXiv:2404.10179_ , 2024.
  * Bamford et al. [2020] C. Bamford, S. Huang, and S. Lucas.  Griddly: A platform for ai research in games.  _arXiv preprint arXiv:2011.06363_ , 2020.
  * Bauer et al. [2023] J. Bauer, K. Baumli, F. Behbahani, A. Bhoopchand, N. Bradley-Schmieg, M. Chang, N. Clay, A. Collister, V. Dasagi, L. Gonzalez, et al.  Human-timescale adaptation in an open-ended task space.  In _International Conference on Machine Learning (ICML) of 2023_ , volume 202, pages 1887–1935. PMLR, 2023.
  * Beattie et al. [2016] C. Beattie, J. Z. Leibo, D. Teplyashin, T. Ward, M. Wainwright, H. Küttler, A. Lefrancq, S. Green, V. Valdés, A. Sadik, et al.  Deepmind Lab.  _arXiv preprint arXiv:1612.03801_ , 2016.
  * Bellemare et al. [2013] M. G. Bellemare, Y. Naddaf, J. Veness, and M. Bowling.  The Arcade Learning Environment: An evaluation platform for general agents.  _Journal of Artificial Intelligence Research_ , 47:253–279, 2013.
  * Carpentier et al. [2021] J. Carpentier, R. Budhiraja, and N. Mansard.  Proximal and Sparse Resolution of Constrained Dynamic Equations.  In _Robotics: Science and Systems of 2021_ , 2021.
  * Chevalier-Boisvert et al. [2023] M. Chevalier-Boisvert, B. Dai, M. Towers, R. de Lazcano, L. Willems, S. Lahlou, S. Pal, P. S. Castro, and J. Terry.  Minigrid & miniworld: Modular & customizable reinforcement learning environments for goal-oriented tasks.  _arXiv preprint arXiv:2306.13831_ , 2023.
  * Cobbe et al. [2020] K. Cobbe, C. Hesse, J. Hilton, and J. Schulman.  Leveraging procedural generation to benchmark reinforcement learning.  _arXiv preprint arXiv:1912.01588_ , 2020.
  * Dosovitskiy et al. [2017] A. Dosovitskiy, G. Ros, F. Codevilla, A. Lopez, and V. Koltun.  CARLA: An open urban driving simulator.  In _the 1st Annual Conference on Robot Learning (CoRL)_ , pages 1–16, 2017.
  * Fan et al. [2022] L. Fan, G. Wang, Y. Jiang, A. Mandlekar, Y. Yang, H. Zhu, A. Tang, D.-A. Huang, Y. Zhu, and A. Anandkumar.  MineDojo: Building open-ended embodied agents with internet-scale knowledge.  _Advances in Neural Information Processing Systems (NeurIPS) of 2022_ , 35:18343–18362, 2022.
  * Gallouédec et al. [2021] Q. Gallouédec, N. Cazin, E. Dellandréa, and L. Chen.  panda-gym: Open-Source Goal-Conditioned Environments for Robotic Learning.  _4th Robot Learning Workshop: Self-Supervised and Lifelong Learning at NeurIPS_ , 2021.
  * Guss et al. [2019] W. H. Guss, B. Houghton, N. Topin, P. Wang, C. Codel, M. Veloso, and R. Salakhutdinov.  MineRL: A large-scale dataset of minecraft demonstrations.  _arXiv preprint arXiv:1907.13440_ , 2019.
  * Huang et al. [2022] S. Huang, R. F. J. Dossa, C. Ye, J. Braga, D. Chakraborty, K. Mehta, and J. G. Araújo.  CleanRL: High-quality single-file implementations of deep reinforcement learning algorithms.  _Journal of Machine Learning Research_ , 23(274):1–18, 2022.
  * Johnson et al. [2016] M. Johnson, K. Hofmann, T. Hutton, and D. Bignell.  The Malmo platform for artificial intelligence experimentation.  In _International Joint Conference on Artificial Intelligence (IJCAI) of 2016_ , volume 16, pages 4246–4247, 2016.
  * Küttler et al. [2020] H. Küttler, N. Nardelli, A. Miller, R. Raileanu, M. Selvatici, E. Grefenstette, and T. Rocktäschel.  The NetHack Learning Environment.  _Advances in Neural Information Processing Systems (NeurIPS) of 2020_ , 33:7671–7684, 2020.
  * Machado et al. [2018] M. C. Machado, M. G. Bellemare, E. Talvitie, J. Veness, M. Hausknecht, and M. Bowling.  Revisiting the Arcade Learning Environment: Evaluation protocols and open problems for general agents.  _Journal of Artificial Intelligence Research_ , 61:523–562, 2018.
  * Moritz et al. [2018] P. Moritz, R. Nishihara, S. Wang, A. Tumanov, R. Liaw, E. Liang, M. Elibol, Z. Yang, W. Paul, M. I. Jordan, et al.  Ray: A distributed framework for emerging AI applications.  In _USENIX Symposium on Operating Systems Design and Implementation (OSDI) of 2018_ , pages 561–577, 2018.
  * Prasanna et al. [2024] S. Prasanna, K. Farid, R. Rajan, and A. Biedenkapp.  Dreaming of many worlds: Learning contextual world models aids zero-shot generalization.  _arXiv preprint arXiv:2403.10967_ , 2024.
  * Raffin et al. [2021] A. Raffin, A. Hill, A. Gleave, A. Kanervisto, M. Ernestus, and N. Dormann.  Stable-Baselines3: Reliable reinforcement learning implementations.  _Journal of Machine Learning Research_ , 22(268):1–8, 2021.
  * Samvelyan et al. [2021] M. Samvelyan, R. Kirk, V. Kurin, J. Parker-Holder, M. Jiang, E. Hambro, F. Petroni, H. Küttler, E. Grefenstette, and T. Rocktäschel.  MiniHack the planet: A sandbox for open-ended reinforcement learning research.  _Datasets and Benchmarks Track of the 2021 NeurIPS_ , 2021.
  * Serrano-Muñoz et al. [2023] A. Serrano-Muñoz, D. Chrysostomou, S. Bøgh, and N. Arana-Arexolaleiba.  skrl: Modular and flexible library for reinforcement learning.  _Journal of Machine Learning Research_ , 24(254):1–9, 2023.
  * Todorov et al. [2012] E. Todorov, T. Erez, and Y. Tassa.  MuJoCo: A physics engine for model-based control.  In _IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) of 2012_ , pages 5026–5033, 2012.
  * Wydmuch et al. [2019] M. Wydmuch, M. Kempka, and W. Jaśkowski.  ViZDoom Competitions: Playing Doom from Pixels.  _IEEE Transactions on Games_ , 11(3):248–259, 2019.


# Scheduling in Wireless Networks using Whittle Index Theory

Karthik GVB$1$, Vivek S. Borkar$2$, Gaurav S. Kasbekar$3$

E-mail addresses<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>$1,2,3$Department of Electrical Engineering,
Indian Institute of Technology (IIT) Bombay, India

###### Abstract

We consider the problem of scheduling packet transmissions in a wireless
network of users while minimizing the energy consumed and the transmission
delay. A challenge is that transmissions of users that are close to each other
mutually interfere, while users that are far apart can transmit simultaneously
without much interference. Each user has a queue of packets that are
transmitted on a single channel and mutually non interfering users reuse the
spectrum. Using the theory of Whittle index for cost minimizing restless
bandits, we design four index-based policies and compare their performance
with that of the well-known policies: Slotted ALOHA, maximum weight
scheduling, quadratic Lyapunov drift, Cella and Cesa Bianchi algorithm, and
two Whittle index based policies from a recently published paper. We make the
code used to perform our simulations publicly available, so that it can be
used for future work by the research community at large.

###### Index Terms:

Wireless Networks, Scheduling, Spatial Reuse, Whittle Index, Energy and Delay
Minimization

##  I Introduction

Recall that multiple users in a wireless network can transmit data
simultaneously on the same channel if they are far apart since there is little
mutual interference. This is known as spatial reuse of spectrum [1] and is
useful for increasing the capacity of wireless networks [1]. In the simplest
case, these mutually far apart users constitute an independent set [2] of
users in the conflict graph [2] corresponding to the network [2]. By
scheduling, we mean that in every slot of transmission, a mutually
independent/ non-interfering set of users is selected to transmit. A challenge
is to accomplish this with low average energy consumption and data
transmission delay.

In this paper, we consider a set of transmitter-receiver pairs of users in a
region and novel scheduling policies by modeling the wireless network of users
using the _restless bandit framework_ [3]. The queue of each user evolves with
time and the constraint is to choose a mutually non-interfering set of users.
In a restless bandit formulation, the _Whittle index theory_ [3] provides a
way to select which users to schedule ($\approx$ arms to activate in the
restless bandit formulation) for minimizing the time-averaged cost. Based on
the Whittle index theory, we design four policies that show better performance
in terms of average cost and average throughtput, than several well-known
policies in most of the scenarios considered.

We represent the wireless network by an undirected graph [2] (fig-1), the
nodes represent the users, and there is an edge between two nodes if the
corresponding users interfere when transmitting data. We model two costs–
“energy cost” and “holding cost”: energy cost refers to the energy consumed
for transmitting packets, which increases with the number of packets
transmitted. Holding cost is proportional to the delay incurred and hence is
proportional to the queue length. The cost incurred in a slot at a user is the
sum of the energy cost and holding cost. The problem is to reduce the time-
averaged total cost incurred by all users in the network. We use Whittle index
theory [3] to solve this problem. As in Whittle’s theory, we relax the hard
constraint of an independent set of users transmitting in each time slot to a
time-averaged constraint and formulate a corresponding unconstrained problem
using Lagrange multipliers, as the original constraint makes the problem
provably hard [4]. As in Whittle’s theory, we decouple the unconstrained
problem into individual problems for each user and define suitable Whittle-
like indices. A distributed algorithm is also proposed for deciding who should
transmit based on the indices for all the users.

We now provide a review of related prior literature. Scheduling in wireless
networks with the objectives of minimizing the energy consumption and/ or
delay has been extensively studied in prior work. A survey of schemes for
delay-aware resource control in a multi-hop wireless network is provided in
[5]. A scheduling scheme for minimizing the energy-expenditure in a time-
varying wireless network with adaptive transmission rates has been provided in
[6]. In [7], the problem of allocating power to links as a function of current
channel states and queue backlogs to stabilize the system while minimizing the
energy expenditure and maintaining low delay in a multiuser network is
studied. In [8], the problem of designing opportunistic scheduling policies
that minimize the average delay in a wireless network with multiple users
sharing a wireless channel is studied. In [9], energy-efficient scheduling
with delay constraints in a multiuser wireless network is studied. The problem
of delay minimization under power constraints for uplink transmission in a
multiuser wireless network is studied in [10]. The problem of minimizing the
transmission power subject to a delay constraint in a multiuser wireless
network is studied in [11]. However, with the exception of the recent works
[12, 1], no work has addressed the problem of scheduling in a wireless network
with the objective of minimizing the energy consumption and delay using the
theory of Whittle index [3]. In the model in [12], at most one user can
successfully transmit at a time on the channel. In this paper, we study a
wireless network that employs spatial reuse of spectrum, allowing multiple
simultaneous transmissions. In [1], two Whittle index based stationary
policies are provided– “Clique Whittle Policy” and “Graphical Whittle Policy”
for the same problem. Among the four policies we introduced in this paper, two
are non stationary policies. Non stationarity is of interest as using past
information for making new decisions may have an advantage of better
performance. But as we infer from the simulation results, non stationary
policies do not give significantly better performance. The performance of the
current four policies is also compared with the policies developed in [1].
They outperform the policies in [1] along with some well-known policies in
most of the cases.

The paper is organized as follows. In Section II, we describe the model and
problem formulation and briefly review the theory of Whittle index. We present
four scheduling algorithms based on Whittle-like indices (referred to as
‘Whittle’ indices henceforth) for this problem in Section III. We present
simulation results in Section IV and conclude in Section V.

##  II Problem formulation and background

###  II-A Model and Problem Formulation

Figure 1: Undirected graph representing a wireless network

We consider a wireless network consisting of $L$ users deployed in a region
and communicating using a single channel. Each user is a transmitter-receiver
pair, with a queue at the transmitter of packets to be sent to the receiver.
Recall that the wireless medium has the property that simultaneous
transmissions by two users that are close to each other interfere with each
other, whereas the channel can be simultaneously used at mutually far apart
locations without interference. To model this, we represent the network using
an undirected graph (fig-1) $\mathcal{G}=(\mathcal{V},\mathcal{E})$, in which
$\mathcal{V}$ is the set of users and there is an edge between two users
$i,j\in\mathcal{V}$ iff the transmissions of users $i$ and $j$ interfere with
each other. Let $\mathcal{N}(i)$ be the set of neighbors of user $i$, i.e.,
the set $\\{j\in\mathcal{V}:\exists(i,j)\in\mathcal{E}\\}$.

Time is divided into slots of equal durations. The queue of user i evolves
according to the dynamics:

$X_{n+1}^{i}=[X_{n}^{i}-\nu_{n}^{i}(X_{n}^{i}\land\Psi^{i})+\xi_{n+1}^{i}]\land
M^{i},$ (1)

where $X_{n}^{i}$ is the length of the queue of user $i$ in slot $n$,
$\xi_{n}^{i}$ is the number of arrivals at the queue of user $i$ in slot $n$,
$M^{i}$ is the capacity of the buffer of user $i$, $\Psi^{i}$ is the maximum
number of packets that may be transmitted by user $i$ in a slot and
$\nu_{n}^{i}$ is $1$ if user $i$ transmits in slot $n$ and $0$ otherwise. We
say that a user is “active” in a slot if it transmits and “passive” if not. We
assume that the number of packet arrivals, $\xi_{n}^{i}$, $n=0,1,2,\dots$, in
different slots are independent and identically distributed (IID) random
variables with distribution $\mu^{i}(\cdot)$.

The cost of holding packets in the queue of user $i$ is $C^{i}$ per packet per
slot. The higher the $C^{i}$, the more stringent the delay requirements of the
packets stored in queue $i$, e.g., $C^{i}$ may be set to a low (resp., high)
value if queue $i$ stores elastic traffic such as file transfer packets
(resp., real-time traffic such as audio and video flow packets). Let
$f^{i}(z)$ be the “energy cost” incurred by user $i$ when it transmits $z$
packets.

Let $\mathcal{N}^{*}(i):=\mathcal{N}(i)\cup\\{i\\}$. If two or more users from
the set $\mathcal{N}^{*}(i)$ transmit in time slot $n$, their transmissions
interfere with each other, leading to the constraints:

$\sum_{j\in\mathcal{N}^{*}(i)}\nu_{n}^{j}\leq 1,\forall i.$ (2)

If a subset of the users in $\mathcal{V}$ transmits in a time slot subject to
(2), then that subset constitutes an independent set of nodes in the graph
$\mathcal{G}=(\mathcal{V},\mathcal{E})$. Let
$Z^{i}_{n}:=X^{i}_{n}\land\Psi^{i}$. We seek to minimize the time-averaged
cost incurred by all users:

$\lim_{N\uparrow\infty}\frac{1}{N}\sum_{n=0}^{N-1}\sum_{i\in\mathcal{V}}E[\nu_{n}^{i}f^{i}(Z_{n}^{i})+C^{i}X_{n}^{i}]$
(3)

subject to the interference constraints (2). That is, our objective is to
select in each slot an independent set of users to activate subject to (2), so
as to minimize (3). The constraint (2) may prevent two mutually non-
interfering users from simultaneously transmitting when they have a common
interfering user, as shown in [1]. Nevertheless, to facilitate the following
analysis, we impose the constraint (2). In Section III-B, we provide an
algorithm for activating users in different time slots, which ensures that
transmitting users form a maximal independent set.

###  II-B Background

We briefly recall here the basics of Whittle index [3] for cost minimizing
restless bandits. Consider a collection of $N\geq 2$ controlled Markov chains
($\approx$ arms of a bandit) $Y^{i}_{n},n\geq 0,i\in{1,\dots,N}$, taking
values in discrete state spaces $S^{i}$, with two modes of operation, active
and passive, and corresponding transition probabilities
$p_{i,1}(t|s),p_{i,0}(t|s)$ and running costs $c_{1}(s),c_{0}(s)$ resp., where
$s,t\in S^{i}$. The control process associated with $i$th chain is
$u_{i}(n),n\geq 0$, taking values in $\\{0,1\\}$ with the interpretation that
value $1$ (resp., $0$) corresponds to active (resp., passive) mode. Thus the
transition probability at time $n$ for the $i$th process is
$p_{i,u_{i}(n)}(\cdot|Y^{i}_{n})$. The objective is to minimize the average
cost

$\limsup_{n\uparrow\infty}\frac{1}{n}E[\sum_{m=0}^{n-1}\sum_{i}c_{u_{i}(m)}(Y_{m}^{i})]$

subject to the per stage constraint

$\sum_{i}u_{i}(n)\leq M,\forall n$

for some $1<M<N$, which couples the problems. This constraint makes the
problem provably hard [13]. The Whittle device is to relax it to the average
constraint

$\limsup_{n\uparrow\infty}\frac{1}{n}E[\sum_{m=0}^{n-1}\sum_{i}u_{i}(m)]\leq
M$

and consider the unconstrained problem of minimizing

$\limsup_{n\uparrow\infty}\frac{1}{n}E[\sum_{m=0}^{n-1}\sum_{i}(c_{u_{i}(m)}(Y_{m}^{i})+\lambda
u_{i}(m))],$ (4)

where $\lambda$ is the Lagrange multiplier. Given $\lambda$, this decouples
into individual control problems of minimizing

$\limsup_{n\uparrow\infty}\frac{1}{n}E[\sum_{m=0}^{n-1}(c_{u_{i}(m)}(Y_{m}^{i})+\lambda
u_{i}(m))]$ (5)

for each $i$. Whittle uses this to motivate the so called Whittle index as
follows. The problem is said to be (Whittle) indexable if the set of passive
states (i.e., the states $Y^{i}_{m}$ for which $u_{i}(m)=0$ is the optimal
action) for each individual problem $i$ monotonically decreases from the whole
state space to the empty set as the ‘tax’ or ‘negative subsidy’ $\lambda$
decreases from $+\infty$ to $-\infty$. If so, the Whittle index for the $i$th
problem is the function $\lambda^{i}:S^{i}\rightmapsto R$ such that
$\lambda^{i}(s):=$ the smallest value of $\lambda$ for which both active and
passive modes are equally desirable in state $s$. The index rule is then to
order, at each time $m$, the current indices $\lambda^{i}(Y^{i}_{m}),1\leq
i\leq N,$ in decreasing order and render active the processes corresponding to
the $M$ lowest indices, breaking ties as per some pre-specified rule, and
render passive the remaining $N-M$ processes. One way to motivate this is as
follows. The relaxation of per stage constraint to time-averaged constraint
means that the actual optimal policy for the latter, i.e., optimal policy for
the unconstrained problem with $\lambda=$ the correct Lagrange multiplier,
will occasionally cause violation of the per stage constraint. The index rule
then goes for an intuitively appealing approximation to it that satisfies the
constraint at each time.

##  III Scheduling based on Whittle indices

###  III-A Definition of Whittle Indices for our Problem

We relax the constraints (2) to the following:

$\limsup_{n\to\infty}\frac{1}{n}E\left[\sum_{m=0}^{n}\sum_{j\in\mathcal{N}^{*}(i)}\nu_{n}^{j}\right]\leq
1,\forall i.$ (6)

We now use a procedure similar to Whittle’s [3]. In this case, (4) gets
replaced by

$\limsup_{n\uparrow\infty}\frac{1}{n}E\left[\sum_{m=0}^{n-1}\sum_{i}(\nu_{m}^{i}f^{i}(Z_{m}^{i})+C^{i}X_{m}^{i}+\lambda^{i}\sum_{j\in\mathcal{N}^{*}(i)}\nu_{m}^{j})\right]$
(7)

leading to the individual problems

$\limsup_{n\uparrow\infty}\frac{1}{n}E\left[\sum_{m=0}^{n-1}\nu_{m}^{i}f^{i}(Z_{m}^{i})+C^{i}X_{m}^{i}+\Lambda^{i}\nu_{m}^{i}\right]$
(8)

for each $i$, with $\Lambda^{i}:=\sum_{j\in\mathcal{N}^{*}(i)}\lambda^{j}$.
Treating $\Lambda^{i}$’s as a surrogate for Whittle tax that is ‘given’, the
problems decouple into individual problems and one can employ Whittle’s logic
to define a Whittle-like index, for a given state $j$, as that value of
$\Lambda^{i}$ for which the active and passive modes are equally desirable at
state $j$. Attractive as this scheme may appear, it is not without problems.
There can be a non-trivial loss of information in the sense that the map from
${\lambda^{i}}$ to ${\Lambda^{i}}$ may not be invertible. Consider, e.g., a
graph with two nodes, say $1$ and $2$, connected by an edge. Then
$\mathcal{N}^{*}(1)=\mathcal{N}^{*}(2)=\\{1,2\\}$. So
$\Lambda^{1}=\Lambda^{2}=\lambda^{1}+\lambda^{2}$. Hence in this example, the
map from ${\lambda^{i}}$ to ${\Lambda^{i}}$ is not invertible. In concrete
terms, moving over to ${\Lambda^{i}}$ may effectively change the constraint
set itself (see [1]).

###  III-B Whittle Index Based Algorithm for Activating Users

In this section, we provide an algorithm for selecting an independent set of
users to activate in a given time slot, assuming that the indices of all the
users in the slot have been already computed. In Section III-C, we provide
four different approaches for computing the whittle indices-— two non
stationary and two stationary methods.

Suppose the indices, $\lambda^{i}(X^{i}_{n})$ of all the users $i\in V$ have
been computed in a given slot $n$. An independent set of users to activate in
the slot is selected as follows. First, all users with empty queues are
declared passive. Then users $i\in V$ for which
$\lambda^{i}(X^{i}_{n})\leq\lambda^{j}(X^{j}_{n})\ \forall j\in\mathcal{N}(i)$
are declared active (ties are broken according to some tie-breaking rule,
e.g., the user with smaller identifier (ID) is declared active). Next, for
every active user $i$, all users $j\in\mathcal{N}(i)$ are declared passive. In
the next step, all users $i\in V$ that are not yet declared passive or active
for which $\lambda^{i}(X^{i}_{n})\leq\lambda^{j}(X^{j}_{n})\ \forall
j\in\mathcal{N}(i)$ that are not already declared passive, are declared
active, and their neighbors are declared passive if already not so. This
process is repeated till all users have been declared either active or
passive. The set of users that are declared active constitute an independent
set. These users transmit in the slot. Furthermore, for implementing the
procedure, at any point in time, a user only requires information that is
available with its neighboring users and therefore the procedure can be
implemented in a distributed manner. Note that this procedure does not satisfy
the constraint (2), but activates an independent set of users.

###  III-C Computation of Whittle Index

We present four different approaches for computing Whittle indices. Recall the
dynamic programming equation for an individual queue $i$ [14]:

$\displaystyle
V^{i}(x^{i})=C^{i}x^{i}+\min_{\nu_{i}\in[0,1]}[\nu^{i}f(x^{i}\wedge\Psi^{i})+(1-\nu^{i})\Lambda^{i}$
(9) $\displaystyle+\sum_{k}V^{i}([x^{i}-\nu^{i}(x^{i}\wedge\Psi^{i})+k]\wedge
M^{i})\mu^{i}(k)]-\beta^{i},$

where $V^{i}(\cdot)$ is the value function, $\beta^{i}$ is the optimal cost
and
$\Lambda^{i}(X^{i}_{n})=\sum_{j\in\mathcal{N}^{*}(i)}\lambda^{j}(X^{i}_{n})$.
Index $\lambda^{i}$ for state $X^{i}_{n}=x^{i}$ is calculated in an iterative
fashion. The following four methods solve a common linear system of equations
in variables $V^{i}(\cdot),\ \beta^{i}$, at each iteration, and then update
$\lambda^{i}$s according to an update rule that distinguishes the methods.

####  III-C1 Non Stationary Type-1

Here Whittle indices are re-computed in each time slot based on Whittle
indices of the preceding slot in two steps:

  * •

Solve the following linear system for $(V^{i}(\cdot),\beta^{i})$ for every arm
$i$:

$\displaystyle\begin{split}V^{i}(y^{i})=&\sum_{k}V^{i}([y^{i}-y^{i}\wedge\Psi^{i}+k]\wedge
M^{i})\mu^{i}(k)-\beta^{i}\\\ &+C^{i}y^{i}+f(y^{i}\wedge\Psi^{i}),\ y^{i}\geq
x^{i},\end{split}$
$\displaystyle\begin{split}V^{i}(y^{i})=&\sum_{k}V^{i}([y^{i}+k]\wedge
M^{i})\mu^{i}(k)+\sum_{j\in\mathcal{N}^{*}(i)}\lambda_{t-1}^{j}\\\
&-\beta^{i}+C^{i}y^{i},\ x^{i}>y^{i}\neq 0,\end{split}$ $\displaystyle
V^{i}(0)=0.$ (10)

  * •

Compute the new Whittle indices using the following $\lambda$ iteration,

$\displaystyle\lambda^{i}_{t}=\lambda^{i}_{t-1}+\gamma[f^{i}(x^{i}\wedge\Psi^{i})-\boxed{\lambda^{i}_{t-1}}$
(11)
$\displaystyle+\sum_{k}\mu^{i}(k)(V^{i}([x^{i}-x^{i}\wedge\Psi^{i}+k]\wedge
M^{i})]$ $\displaystyle-V^{i}([x^{i}+k]\wedge M^{i}).$

####  III-C2 Non Stationary Type-2

As above, but replace (11) by

$\displaystyle\begin{split}\lambda^{i}_{t}=&\lambda^{i}_{t-1}+\gamma[f^{i}(x^{i}\wedge\Psi^{i})-\boxed{\sum_{j\in\mathcal{N}^{*}(i)}\lambda^{j}_{t-1}}\\\
&+\sum_{k}\mu^{i}(k)(V^{i}([x^{i}-x^{i}\wedge\Psi^{i}+k]\wedge M^{i})\\\
&-V^{i}([x^{i}+k])\wedge M^{i})].\end{split}$ (12)

####  III-C3 New Stationary Type-1

This policy is a stationary policy, so the Whittle indices can be computed
ahead of system/ simulation start. Here we perform a few iterations to compute
the $\lambda$s to estimate the actual Whittle indices as follows. Initialize
all $\lambda$s to zero. Then at each step, solve the above linear system and
update the indices according to

$\displaystyle\begin{split}\lambda^{i}_{n}=&\lambda^{i}_{n-1}+\gamma[f^{i}(x^{i}\wedge\Psi^{i})-\boxed{\lambda^{i}_{n-1}}\\\
&+\sum_{k}\mu^{i}(k)(V^{i}([x^{i}-x^{i}\wedge\Psi^{i}+k]\wedge M^{i})\\\
&-V^{i}([x^{i}+k])\wedge M^{i})].\end{split}$ (13)

After executing these steps a number of times, the final $\lambda$s are taken
to be the indices for the given state of the system.

####  III-C4 New Stationary Type-2

As above except that the $\lambda$ iteration is replaced by

$\displaystyle\begin{split}\lambda^{i}_{n}=&\lambda^{i}_{n-1}+\gamma[f^{i}(x^{i}\wedge\Psi^{i})-\boxed{\sum_{j\in\mathcal{N}^{*}(i)}\lambda^{j}_{t-1}}\\\
&+\sum_{k}\mu^{i}(k)(V^{i}([x^{i}-x^{i}\wedge\Psi^{i}+k]\wedge M^{i})\\\
&-V^{i}([x^{i}+k])\wedge M^{i})].\end{split}$ (14)

####  III-C5 Explanation for Above Computational Schemes

The linear system (• ‣ III-C1) above constitutes the Poisson equation (i.e.,
constant policy dynamic programming equation) for the chain controlled by a
fixed stationary Markov policy, viz., the threshold policy with threshold
$x^{i}$. Under irreducibility hypothesis (more generally, uni-chain property,
see, e.g., [14]), this has a solution $(V^{i},\beta^{i})$ where $\beta^{i}$ is
uniquely given as the average cost under this policy and the ‘value function’
$V^{i}$ is unique up to an additive constant. The additional condition
$V^{i}(0)=0$ then renders it unique. The iterates in the four approaches (11),
(12), (13), (14) are also similar except for the terms present in a box. They
make incremental adjustments in $\lambda^{i}$s so as to force the defining
equality for the Whittle index.

##  IV Simulations

In this section, we evaluate the performances of the proposed algorithms and
compare them with those of the policies proposed in [1], the well known
Slotted ALOHA [15], maximum-weight scheduling (MWS) [16], quadratic Lyapunov
drift [17] algorithms, and an algorithm recently proposed by Cella and Cesa-
Bianchi [18], via simulations (see our code [19] for details). The performance
is evaluated in terms of two metrics– average cost and average total number of
packets dropped per time slot-– at all the users in the network. Note that
penalizing queue length automatically penalizes packet drops. Putting an
explicit penalty on packet drops adds an extra cost for the state (the buffer
length), a cost that retains the monotonicity and (discrete) convexity
properties of the running cost and does not affect our heuristic argument
leading to the proposed policy. It is expected to decrease the mean packet
drops at the expense of mean energy cost. This is a topic for future research.

###  IV-A Simulation Model

In our simulations [19], we consider the model in Section II-A with $L=20$
users and buffer capacity $M^{i}=100$ for each user $i\in V$. The location of
each user is selected uniformly at random in a square of dimensions $1\times
1$ unit. Two users are neighbors iff the distance between them is less than a
threshold $d$, which is a parameter. Unless otherwise mentioned, we use
$d=0.6$ units throughout the simulations. Let $\Psi^{i}$ be the maximum number
of packets that may be transmitted by user $i$ in a given slot. For the index
based algorithms, we consider two cases: (i) $\Psi^{i}=\infty$, and (ii)
$\Psi^{i}$ is uniformly distributed between $1$ and $M^{i}/5$ for user $i$,
independent of other users. We refer to cases (i) and (ii) as the
“unrestricted transmission” and “restricted transmission”, respectively. Note
that in case (i), a user that transmits in a time slot sends all the packets
in its queue. In our simulations, unless otherwise mentioned, under the
Slotted ALOHA, Max-Weight Scheduling, quadratic Lyapunov drift and Cella and
Cesa-Bianchi’s algorithms, the value $\Psi^{i}$ for user $i$ is the same as
that in the restricted case of the index based algorithms. We assume that the
number of packets $\xi^{i}_{n}$ that arrive at user $i$ in time slot $n$ is a
Poisson random variable with mean $l^{i}$. Also, unless otherwise mentioned,
$l^{i}$ is selected uniformly at random to be between $1$ and $M^{i}/10$ for
each $i$, independent of other users. We use $\theta=200$ in the quadratic
Lyapunov drift algorithm.

###  IV-B Simulation Results

In the plots below, by “large arrival rates” (respectively, “small arrival
rates”), we mean that $l^{i}$ is chosen uniformly at random between $1$ and
$M^{i}/8$ (respectively, between $1$ and $M^{i}/15$). Figs. 2(a), 2(b), 2(c)
and 2(d) (respectively, 3(a), 3(b), 3(c) and 3(d)) compare the performances of
Non stationary type-1 policy, Non stationary type-2 policy, New stationary
type-1 policy, New stationary type-2 policy, the policies in [1]– “Clique
Whittle Policy” and “Graphical Whittle Policy”, Slotted ALOHA, Max Weight
Scheduling (MWS), quadratic Lyapunov drift algorithm, and Cella and Cesa-
Bianchi’s algorithm in terms of average cost (respectively, average total
number of packets dropped by all users in the network per time slot), for the
cases with large/ small arrival rates and restricted/ unrestricted
transmissions, respectively.

As per the average cost (Figs. 2(a), 2(b), 2(c) and 2(d)), the New stationary
policies: type-1 and type-2 outperformed all the other policies except for the
case of small arrival rates with restricted transmissions where the Cella and
Cesa-Bianchi’s algorithm is the optimal, but there is just a marginal
difference between the New stationary policies and the latter. As per the
packets dropped (Figs. 3(a), 3(b), 3(c) and 3(d)), the proposed stationary
policies do not have an upper hand and there isn’t one best policy, i.e.,
optimal in all cases. The Whittle policies in [1] relatively have better
performance by comparison in all cases. We consider the preferred policy to be
the New stationary policy type-1 as it showed better performance in many
cases. The intuition behind the observed results is that resetting the
$\lambda$ iterates to zero as in the new stationary policies removes the undue
influence of the past. Similarly, having the term in the box depend on the
neighboring $\lambda$’s introduces a ‘competitive’ aspect in the coupling
between neighboring nodes and worsens the performance. A detailed analysis of
these phenomena are a subject for future work.

##  V Conclusions and future work

We proposed four Whittle index based scheduling policies for scheduling packet
transmissions with the objective of minimizing the energy consumption and data
transmission delay of users in a wireless network in which spatial reuse of
spectrum is employed. Two of the policies are non stationary and two are
stationary. We evaluated the performance of these policies via extensive
simulations and showed that they outperform the well-known Slotted ALOHA,
maximum-weight scheduling, quadratic Lyapunov drift, algorithm proposed by
Cella and Cesa-Bianchi and the two Whittle index based policies (Clique and
Graphical Whittle policies) in [1]. A potential direction for future research
is to develop analytical bases for these schemes and their improved variants.
Another direction for future work is to extend the results of this paper to
the case where the users of the network use millimeter wave (mmWave) spectrum
and each transmitter-receiver pair uses directional transmissions
(beamforming) for exchanging information [20].

Acknowledgments VSB was supported by a S. S. Bhatnagar Fellowship from the
Govt. of India. The work of GSK was supported in part by the project with code
RD/0121-MEITY01-001.

## References

  * [1] Vivek S. Borkar, Shantanu Choudhary, Vaibhav Kumar Gupta and Gaurav S. Kasbekar  “Scheduling in wireless networks with spatial reuse of spectrum as restless bandits”  In _Performance Evaluation_ 149-150, 2021, pp. 102208
  * [2] Reinhard Diestel  “Graph theory (2nd edn.)”  In _Springer-Verlag_ , 2001
  * [3] P. Whittle  “Restless bandits: activity allocation in a changing world”  In _Journal of Applied Probability_ 25.A Cambridge University Press, 1988, pp. 287–298
  * [4] Christos H. Papadimitriou and John N. Tsitsiklis  “The Complexity of Optimal Queuing Network Control”  In _Mathematics of Operations Research_ 24.2, 2020, pp. 293–305
  * [5] Ying Cui et al.  “A Survey on Delay-Aware Resource Control for Wireless Systems—Large Deviation Theory, Stochastic Lyapunov Drift, and Distributed Stochastic Learning”  In _IEEE Transactions on Information Theory_ 58.3, 2012, pp. 1677–1701
  * [6] M.J. Neely  “Energy optimal control for time-varying wireless networks”  In _IEEE Transactions on Information Theory_ 52.7, 2006, pp. 2915–2934
  * [7] Michael J. Neely  “Optimal Energy and Delay Tradeoffs for Multiuser Wireless Downlinks”  In _IEEE Transactions on Information Theory_ 53.9, 2007, pp. 3095–3113
  * [8] Bilal Sadiq, Seung Jun Baek and Gustavo Veciana  “Delay-Optimal Opportunistic Scheduling and Approximations: The Log Rule”  In _IEEE/ACM Transactions on Networking_ 19.2, 2011, pp. 405–418
  * [9] Nitin Salodkar, Abhay Karandikar and Vivek S. Borkar  “A Stable Online Algorithm for Energy-Efficient Multiuser Scheduling”  In _IEEE Transactions on Mobile Computing_ 9.10, 2010, pp. 1391–1406
  * [10] Mohammad Moghadari, Ekram Hossain and Long Bao Le  “Delay-Optimal Distributed Scheduling in Multi-User Multi-Relay Cellular Wireless Networks”  In _IEEE Transactions on Communications_ 61.4, 2013, pp. 1349–1360
  * [11] Xi Zhang and Jia Tang  “Power-Delay Tradeoff over Wireless Networks”  In _IEEE Transactions on Communications_ 61.9, 2013, pp. 3673–3684
  * [12] Vivek S. Borkar, Gaurav S. Kasbekar, Sarath Pattathil and Priyesh Y. Shetty  “Opportunistic Scheduling as Restless Bandits”  In _IEEE Transactions on Control of Network Systems_ 5.4, 2018, pp. 1952–1961
  * [13] Christos H. Papadimitriou and John N. Tsitsiklis  “The Complexity of Optimal Queuing Network Control”  In _Mathematics of Operations Research_ 24.2 INFORMS, 1999, pp. 293–305
  * [14] Martin L Puterman  “Markov decision processes: discrete stochastic dynamic programming”  John Wiley & Sons, 2014
  * [15] James F Kurose  “Computer networking: A top-down approach featuring the internet, 3/E”  Pearson Education India, 2005
  * [16] L. Tassiulas and A. Ephremides  “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks”  In _IEEE Transactions on Automatic Control_ 37.12, 1992, pp. 1936–1948
  * [17] M.J. Neely  “Energy optimal control for time-varying wireless networks”  In _IEEE Transactions on Information Theory_ 52.7, 2006, pp. 2915–2934
  * [18] Leonardo Cella and Nicoló Cesa-Bianchi  “Stochastic Bandits with Delay-Dependent Payoffs”  In _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ 108, Proceedings of Machine Learning Research  PMLR, 2020, pp. 1168–1177
  * [19] GVB Karthik  “whittle policies”  URL: https://github.com/karthikgvb/whittle_scheduling_policies.git
  * [20] Santosh Kumar Singh, Vivek Shripad Borkar and Gaurav Sudhir Kasbekar  “User Association in Dense mmWave Networks as Restless Bandits”  In _IEEE Transactions on Vehicular Technology_ IEEE, 2022

(a) Large arrival rates, restricted transmissions

(b) Large arrival rates, unrestricted transmissions

(c) Small arrival rates, restricted transmissions

(d) Small arrival rates, unrestricted transmissions

Figure 2: Average Cost Comparison

(a) Large arrival rates, restricted transmissions

(b) Large arrival rates, unrestricted transmissions

(c) Small arrival rates, restricted transmissions

(d) Small arrival rates, unrestricted transmissions

Figure 3: Average Packets Dropped Comparison