Search

This paper addresses the exploration-exploitation dilemma inherent in decision-making, focusing on multi-armed bandit problems. The problems involve an agent deciding whether to exploit current knowledge for immediate gains or explore new avenues for potential long-term rewards. We here introduce a novel algorithm, approximate information maximization (AIM), which employs an analytical approximation of the entropy gradient to choose which arm to pull at each point in time. AIM matches the performance of Infomax and Thompson sampling while also offering enhanced computational speed, determinism, and tractability. Empirical evaluation of AIM indicates its compliance with the Lai & Robbins asymptotic bound and demonstrates its robustness for a range of priors. Its expression is tunable, which allows for specific optimization in various settings.

This thesis seeks to quantify the time to first passage over a target (FPT) of a class of random walks for which the walker is endowed with long-range memory effects that emerge from the interaction of the walker with the territory he has visited at previous times. The first part is devoted to the study of the links between aging and persistence exponent. We present examples of aging processes that are asymptotically diffusive and that are characterized by anomalous persistence exponents. In a second part, we establish that the attractively reinforced walks fall into different categories for which we have characterized their aging and first-pass properties. We highlight the importance of such reinforcement effects in the analysis of real cell trajectories. In a third part, we show that these long-range memory effects can induce non-trivial aging, persistence and transience exponents in both infinite and confined geometries. In particular, we quantify the dependence of the FPT distribution in confinement on different geometric parameters. In a fourth part, we study the first-pass properties of a walker following a generalized Langevin equation in the presence of a harmonic potential. From the position of the walker in the future of the FPT, we predict the values of the mean time of first passage. Finally, we address the question of the joint distribution of the first-pass time and the number of distinct sites visited at the FPT time., Cette thèse cherche à quantifier le temps de premier passage sur une cible (FPT) d'une classe de marches aléatoires pour lesquelles le marcheur est doté d'effets de mémoire à longue portée qui émergent de l'interaction de celui-ci avec le territoire qu'il a visité à des temps antérieurs. La première partie est consacrée à l'étude des liens entre vieillissement et exposant de persistance. Nous y présentons des exemples de processus vieillissants, asymptotiquement diffusifs, et qui sont caractérisés par des exposants de persistance anormaux. Dans une seconde partie, nous établissons que les marches à renforcement attractif se répartissent selon différentes catégories pour lesquelles nous avons caractérisé leurs propriétés de vieillissement et de premier passage. Nous soulignons l'importance de tels effets de renforcement dans l'analyse de trajectoires cellulaires réelles. Dans une troisième partie, nous montrons que ces effets de mémoire à longue portée peuvent induire un vieillissement et des exposants de persistance et de transience non triviaux à la fois dans des géométries infinies et confinées. Nous quantifions notamment la dépendance de la distribution du FPT en confinement envers les différents paramètres géométriques. Dans une quatrième partie, nous entamons l'étude des propriétés de premier passage d'un marcheur suivant une équation de Langevin généralisée en présence d'un potentiel harmonique. À partir de la position du marcheur dans le futur du FPT, nous prédisons les valeurs du temps moyen de premier passage. Enfin, nous abordons la question de la distribution jointe du temps de premier passage et du nombre de sites distincts visités à l'instant du FPT.