Palo Alto Networks
AI Insights
- Reranking models in IR: Models that refine the ranking of documents based on their relevance to a user's query. [3]
- The evolution of reranking models in IR has been shaped by advancements in large language models (LLMs) and their applications. [2]
- Researchers have explored various techniques to fine-tune LLMs for personalized ranking, knowledge distillation, and prompt engineering. [1]
Abstract
Reranking is a critical stage in contemporary information retrieval (IR) systems, improving the relevance of the user-presented final results by honing initial candidate sets. This paper is a thorough guide to examine the changing reranker landscape and offer a clear view of the advancements made in reranking methods. We present a comprehensive survey of reranking models employed in IR, particularly within modern Retrieval Augmented Generation (RAG) pipelines, where retrieved documents notably influence output quality. We embark on a chronological journey through the historical trajectory of reranking techniques, starting with foundational approaches, before exploring the wide range of sophisticated neural network architectures such as cross-encoders, sequence-generation models like T5, and Graph Neural Networks (GNNs) utilized for structural information. Recognizing the computational cost of advancing neural rerankers, we analyze techniques for enhancing efficiency, notably knowledge distillation for creating competitive, lighter alternatives. Furthermore, we map the emerging territory of integrating Large Language Models (LLMs) in reranking, examining novel prompting strategies and fine-tuning tactics. This survey seeks to elucidate the fundamental ideas, relative effectiveness, computational features, and real-world trade-offs of various reranking strategies. The survey provides a structured synthesis of the diverse reranking paradigms, highlighting their underlying principles and comparative strengths and weaknesses.
Reranking is a critical stage in contemporary information retrieval (IR) systems, improving the relevance of the user-presented final results by honing initial candidate sets. This paper is a thorough guide to examine the changing reranker landscape and offer a clear view of the advancements made in reranking methods. We present a comprehensive survey of reranking models employed in IR, particularly within modern Retrieval Augmented Generation (RAG) pipelines, where retrieved documents notably influence output quality. We embark on a chronological journey through the historical trajectory of reranking techniques, starting with foundational approaches, before exploring the wide range of sophisticated neural network architectures such as cross-encoders, sequence-generation models like T5, and Graph Neural Networks (GNNs) utilized for structural information. Recognizing the computational cost of advancing neural rerankers, we analyze techniques for enhancing efficiency, notably knowledge distillation for creating competitive, lighter alternatives. Furthermore, we map the emerging territory of integrating Large Language Models (LLMs) in reranking, examining novel prompting strategies and fine-tuning tactics. This survey seeks to elucidate the fundamental ideas, relative effectiveness, computational features, and real-world trade-offs of various reranking strategies. The survey provides a structured synthesis of the diverse reranking paradigms, highlighting their underlying principles and comparative strengths and weaknesses.
Why we are recommending this paper?
Due to your Interest in: Information Retrieval
This paper directly addresses information retrieval, a core interest, and explores the latest advancements in reranking models – a critical component of search systems. Given the focus on large language models, it aligns well with the user's interest in deep learning and search.
Due to your Interest in: Information Retrieval
This paper directly addresses information retrieval, a core interest, and explores the latest advancements in reranking models – a critical component of search systems. Given the focus on large language models, it aligns well with the user's interest in deep learning and search.
National Taiwan Universty
Abstract
Equipping large language models (LLMs) with search engines via reinforcement learning (RL) has emerged as an effective approach for building search agents. However, overreliance on search introduces unnecessary cost and risks exposure to noisy or malicious content, while relying solely on parametric knowledge risks hallucination. The central challenge is to develop agents that adaptively balance parametric knowledge with external search, invoking search only when necessary. Prior work mitigates search overuse by shaping rewards around the number of tool calls. However, these penalties require substantial reward engineering, provide ambiguous credit assignment, and can be exploited by agents that superficially reduce calls. Moreover, evaluating performance solely through call counts conflates necessary and unnecessary search, obscuring the measurement of true adaptive behavior. To address these limitations, we first quantify the self-knowledge awareness of existing search agents via an F1-based decision metric, revealing that methods such as Search-R1 often overlook readily available parametric knowledge. Motivated by these findings, we propose AdaSearch, a simple two-stage, outcome-driven RL framework that disentangles problem solving from the decision of whether to invoke search, and makes this decision process explicit and interpretable. This transparency is crucial for high-stakes domains such as finance and medical question answering, yet is largely neglected by prior approaches. Experiments across multiple model families and sizes demonstrate that AdaSearch substantially improves knowledge-boundary awareness, reduces unnecessary search calls, preserves strong task performance, and offers more transparent, interpretable decision behaviors.
Equipping large language models (LLMs) with search engines via reinforcement learning (RL) has emerged as an effective approach for building search agents. However, overreliance on search introduces unnecessary cost and risks exposure to noisy or malicious content, while relying solely on parametric knowledge risks hallucination. The central challenge is to develop agents that adaptively balance parametric knowledge with external search, invoking search only when necessary. Prior work mitigates search overuse by shaping rewards around the number of tool calls. However, these penalties require substantial reward engineering, provide ambiguous credit assignment, and can be exploited by agents that superficially reduce calls. Moreover, evaluating performance solely through call counts conflates necessary and unnecessary search, obscuring the measurement of true adaptive behavior. To address these limitations, we first quantify the self-knowledge awareness of existing search agents via an F1-based decision metric, revealing that methods such as Search-R1 often overlook readily available parametric knowledge. Motivated by these findings, we propose AdaSearch, a simple two-stage, outcome-driven RL framework that disentangles problem solving from the decision of whether to invoke search, and makes this decision process explicit and interpretable. This transparency is crucial for high-stakes domains such as finance and medical question answering, yet is largely neglected by prior approaches. Experiments across multiple model families and sizes demonstrate that AdaSearch substantially improves knowledge-boundary awareness, reduces unnecessary search calls, preserves strong task performance, and offers more transparent, interpretable decision behaviors.
Why we are recommending this paper?
Due to your Interest in: Search
This work investigates reinforcement learning for LLMs, a burgeoning area of research that aligns with the user's interest in deep learning and personalization. The focus on search agents within LLMs is particularly relevant to the user's interest in search and ranking.
Due to your Interest in: Search
This work investigates reinforcement learning for LLMs, a burgeoning area of research that aligns with the user's interest in deep learning and personalization. The focus on search agents within LLMs is particularly relevant to the user's interest in search and ranking.
Zhejiang University
AI Insights
- The proposed approach demonstrates the importance of rich contextual and behavioral signals for personalization, highlighting the need for more nuanced understanding of user characteristics and behaviors. [3]
- Previous work in user profile and recommender systems emphasizes the importance of rich contextual and behavioral signals for personalization. [3]
- Personalization in Conversational AI The paper presents a new approach to making conversational AI more personalized. [3]
- It focuses on understanding users' preferences and adapting to their needs, rather than relying solely on static information. [3]
- The paper presents a comprehensive approach to personalization in conversational AI, focusing on aligning large language models (LLMs) with user preferences. [2]
Abstract
The deployment of Large Language Models (LLMs) in interactive systems necessitates a deep alignment with the nuanced and dynamic preferences of individual users. Current alignment techniques predominantly address universal human values or static, single-turn preferences, thereby failing to address the critical needs of long-term personalization and the initial user cold-start problem. To bridge this gap, we propose PersonalAgent, a novel user-centric lifelong agent designed to continuously infer and adapt to user preferences. PersonalAgent constructs and dynamically refines a unified user profile by decomposing dialogues into single-turn interactions, framing preference inference as a sequential decision-making task. Experiments show that PersonalAgent achieves superior performance over strong prompt-based and policy optimization baselines, not only in idealized but also in noisy conversational contexts, while preserving cross-session preference consistency. Furthermore, human evaluation confirms that PersonalAgent excels at capturing user preferences naturally and coherently. Our findings underscore the importance of lifelong personalization for developing more inclusive and adaptive conversational agents. Our code is available here.
The deployment of Large Language Models (LLMs) in interactive systems necessitates a deep alignment with the nuanced and dynamic preferences of individual users. Current alignment techniques predominantly address universal human values or static, single-turn preferences, thereby failing to address the critical needs of long-term personalization and the initial user cold-start problem. To bridge this gap, we propose PersonalAgent, a novel user-centric lifelong agent designed to continuously infer and adapt to user preferences. PersonalAgent constructs and dynamically refines a unified user profile by decomposing dialogues into single-turn interactions, framing preference inference as a sequential decision-making task. Experiments show that PersonalAgent achieves superior performance over strong prompt-based and policy optimization baselines, not only in idealized but also in noisy conversational contexts, while preserving cross-session preference consistency. Furthermore, human evaluation confirms that PersonalAgent excels at capturing user preferences naturally and coherently. Our findings underscore the importance of lifelong personalization for developing more inclusive and adaptive conversational agents. Our code is available here.
Why we are recommending this paper?
Due to your Interest in: Personalization
This paper tackles the crucial problem of personalization in interactive systems, directly addressing the user's interest in personalization and ranking. The exploration of aligning LLMs with individual user preferences is highly relevant to the user's focus on personalization.
Due to your Interest in: Personalization
This paper tackles the crucial problem of personalization in interactive systems, directly addressing the user's interest in personalization and ranking. The exploration of aligning LLMs with individual user preferences is highly relevant to the user's focus on personalization.
UC Santa Barbara
AI Insights
- The study examines the performance of various language models on a dataset with diverse user profiles, highlighting the importance of personality traits and conversation style in determining likability. [3]
- The results show that top-performing models (GPT-5 and Claude Sonnet 4) are stable across different user types, while others struggle to adapt. [3]
- The introduction of Dynamic User Profile (DUP) improves performance for top models without additional training, indicating the potential of lightweight preference tracking. [3]
- Likability: The degree to which a language model is perceived as likable or relatable by users. [3]
- Conversation style preferences: The way individuals prefer to communicate, including aspects such as directness, formality, and conversation length. [3]
- Lightweight preference tracking (DUP) shows promise in improving performance without additional training. [3]
- The study's taxonomy of personality traits and conversation style preferences provides a comprehensive framework for understanding user behavior. [2]
Abstract
A personalized LLM should remember user facts, apply them correctly, and adapt over time to provide responses that the user prefers. Existing LLM personalization benchmarks are largely centered on two axes: accurately recalling user information and accurately applying remembered information in downstream tasks. We argue that a third axis, likability, is both subjective and central to user experience, yet under-measured by current benchmarks. To measure likability holistically, we introduce LikeBench, a multi-session, dynamic evaluation framework that measures likability across multiple dimensions by how much an LLM can adapt over time to a user's preferences to provide more likable responses. In LikeBench, the LLMs engage in conversation with a simulated user and learn preferences only from the ongoing dialogue. As the interaction unfolds, models try to adapt to responses, and after each turn, they are evaluated for likability across seven dimensions by the same simulated user. To the best of our knowledge, we are the first to decompose likability into multiple diagnostic metrics: emotional adaptation, formality matching, knowledge adaptation, reference understanding, conversation length fit, humor fit, and callback, which makes it easier to pinpoint where a model falls short. To make the simulated user more realistic and discriminative, LikeBench uses fine-grained, psychologically grounded descriptive personas rather than the coarse high/low trait rating based personas used in prior work. Our benchmark shows that strong memory performance does not guarantee high likability: DeepSeek R1, with lower memory accuracy (86%, 17 facts/profile), outperformed Qwen3 by 28% on likability score despite Qwen3's higher memory accuracy (93%, 43 facts/profile). Even SOTA models like GPT-5 adapt well in short exchanges but show only limited robustness in longer, noisier interactions.
A personalized LLM should remember user facts, apply them correctly, and adapt over time to provide responses that the user prefers. Existing LLM personalization benchmarks are largely centered on two axes: accurately recalling user information and accurately applying remembered information in downstream tasks. We argue that a third axis, likability, is both subjective and central to user experience, yet under-measured by current benchmarks. To measure likability holistically, we introduce LikeBench, a multi-session, dynamic evaluation framework that measures likability across multiple dimensions by how much an LLM can adapt over time to a user's preferences to provide more likable responses. In LikeBench, the LLMs engage in conversation with a simulated user and learn preferences only from the ongoing dialogue. As the interaction unfolds, models try to adapt to responses, and after each turn, they are evaluated for likability across seven dimensions by the same simulated user. To the best of our knowledge, we are the first to decompose likability into multiple diagnostic metrics: emotional adaptation, formality matching, knowledge adaptation, reference understanding, conversation length fit, humor fit, and callback, which makes it easier to pinpoint where a model falls short. To make the simulated user more realistic and discriminative, LikeBench uses fine-grained, psychologically grounded descriptive personas rather than the coarse high/low trait rating based personas used in prior work. Our benchmark shows that strong memory performance does not guarantee high likability: DeepSeek R1, with lower memory accuracy (86%, 17 facts/profile), outperformed Qwen3 by 28% on likability score despite Qwen3's higher memory accuracy (93%, 43 facts/profile). Even SOTA models like GPT-5 adapt well in short exchanges but show only limited robustness in longer, noisier interactions.
Why we are recommending this paper?
Due to your Interest in: Personalization
The paper's focus on evaluating LLMs for personalization, specifically through subjective likability, aligns strongly with the user's interest in personalization and ranking. It offers a valuable benchmark for assessing the effectiveness of personalization techniques.
Due to your Interest in: Personalization
The paper's focus on evaluating LLMs for personalization, specifically through subjective likability, aligns strongly with the user's interest in personalization and ranking. It offers a valuable benchmark for assessing the effectiveness of personalization techniques.
University of Bonn
AI Insights
- They show that this adjusted strategy attains the same X-coordinates in the free space as the original part of the path, while potentially having a larger Y-coordinate. [3]
- The authors use a budget-based approach to ensure that the adjusted strategy has the same path length as the original part, and they calculate the return points during the movement to guarantee this property. [3]
- They also show that the adjusted strategy is optimal in terms of path length. [3]
- The authors use mathematical techniques such as calculus and optimization to derive the results. [3]
- The paper discusses the application and adaptation of the cow path strategy to the terrain search problem, highlighting the importance of exploiting the terrain's slope to minimize the path length. [3]
- cow path problem: a classic problem in computational geometry where an agent must find the shortest path between two points while avoiding obstacles. [3]
- The paper presents a new strategy for searching in a terrain with obstacles, which is an extension of the traditional cow path problem. [2]
- pure strategy: a starting point for the adjusted strategy, which is used as a basis for the adjustments made according to the terrain. [1]
Abstract
We consider the problem of searching for rays (or lines) in the half-plane. The given problem turns out to be a very natural extension of the cow-path problem that is lifted into the half-plane and the problem can also directly be motivated by a 1.5-dimensional terrain search problem. We present and analyse an efficient strategy for our setting and guarantee a competitive ratio of less than 9.12725 in the worst case and also prove a lower bound of at least 9.06357 for any strategy. Thus the given strategy is almost optimal, the gap is less than 0.06368. By appropriate adjustments for the terrain search problem we can improve on former results and present geometrically motivated proof arguments. As expected, the terrain itself can only be helpful for the searcher that competes against the unknown shortest path. We somehow extract the core of the problem.
We consider the problem of searching for rays (or lines) in the half-plane. The given problem turns out to be a very natural extension of the cow-path problem that is lifted into the half-plane and the problem can also directly be motivated by a 1.5-dimensional terrain search problem. We present and analyse an efficient strategy for our setting and guarantee a competitive ratio of less than 9.12725 in the worst case and also prove a lower bound of at least 9.06357 for any strategy. Thus the given strategy is almost optimal, the gap is less than 0.06368. By appropriate adjustments for the terrain search problem we can improve on former results and present geometrically motivated proof arguments. As expected, the terrain itself can only be helpful for the searcher that competes against the unknown shortest path. We somehow extract the core of the problem.
Why we are recommending this paper?
Due to your Interest in: Search
This paper presents a novel approach to ray searching, a fundamental problem in computer vision and robotics – areas that often intersect with information retrieval and ranking. The use of half-plane constraints is a sophisticated technique relevant to the user's interest in search.
Due to your Interest in: Search
This paper presents a novel approach to ray searching, a fundamental problem in computer vision and robotics – areas that often intersect with information retrieval and ranking. The use of half-plane constraints is a sophisticated technique relevant to the user's interest in search.
JDcom
Abstract
Dense retrieval has become the industry standard in large-scale information retrieval systems due to its high efficiency and competitive accuracy. Its core relies on a coarse-to-fine hierarchical architecture that enables rapid candidate selection and precise semantic matching, achieving millisecond-level response over billion-scale corpora. This capability makes it essential not only in traditional search and recommendation scenarios but also in the emerging paradigm of generative recommendation driven by large language models, where semantic IDs-themselves a form of coarse-to-fine representation-play a foundational role. However, the widely adopted dual-tower encoding architecture introduces inherent challenges, primarily representational space misalignment and retrieval index inconsistency, which degrade matching accuracy, retrieval stability, and performance on long-tail queries. These issues are further magnified in semantic ID generation, ultimately limiting the performance ceiling of downstream generative models. To address these challenges, this paper proposes a simple and effective framework named SCI comprising two synergistic modules: a symmetric representation alignment module that employs an innovative input-swapping mechanism to unify the dual-tower representation space without adding parameters, and an consistent indexing with dual-tower synergy module that redesigns retrieval paths using a dual-view indexing strategy to maintain consistency from training to inference. The framework is systematic, lightweight, and engineering-friendly, requiring minimal overhead while fully supporting billion-scale deployment. We provide theoretical guarantees for our approach, with its effectiveness validated by results across public datasets and real-world e-commerce datasets.
Dense retrieval has become the industry standard in large-scale information retrieval systems due to its high efficiency and competitive accuracy. Its core relies on a coarse-to-fine hierarchical architecture that enables rapid candidate selection and precise semantic matching, achieving millisecond-level response over billion-scale corpora. This capability makes it essential not only in traditional search and recommendation scenarios but also in the emerging paradigm of generative recommendation driven by large language models, where semantic IDs-themselves a form of coarse-to-fine representation-play a foundational role. However, the widely adopted dual-tower encoding architecture introduces inherent challenges, primarily representational space misalignment and retrieval index inconsistency, which degrade matching accuracy, retrieval stability, and performance on long-tail queries. These issues are further magnified in semantic ID generation, ultimately limiting the performance ceiling of downstream generative models. To address these challenges, this paper proposes a simple and effective framework named SCI comprising two synergistic modules: a symmetric representation alignment module that employs an innovative input-swapping mechanism to unify the dual-tower representation space without adding parameters, and an consistent indexing with dual-tower synergy module that redesigns retrieval paths using a dual-view indexing strategy to maintain consistency from training to inference. The framework is systematic, lightweight, and engineering-friendly, requiring minimal overhead while fully supporting billion-scale deployment. We provide theoretical guarantees for our approach, with its effectiveness validated by results across public datasets and real-world e-commerce datasets.
Why we are recommending this paper?
Due to your Interest in: Information Retrieval
Due to your Interest in: Information Retrieval
The University of Hongk
Abstract
Cryogenic electron microscopy (Cryo-EM) has become an essential tool for capturing high-resolution biological structures. Despite its advantage in visualizations, the large storage size of Cryo-EM data file poses significant challenges for researchers and educators. This paper investigates the application of deep learning, specifically implicit neural representation (INR), to compress Cryo-EM biological data. The proposed approach first extracts the binary map of each file according to the density threshold. The density map is highly repetitive, ehich can be effectively compressed by GZIP. The neural network then trains to encode spatial density information, allowing the storage of network parameters and learnable latent vectors. To improve reconstruction accuracy, I further incorporate the positional encoding to enhance spatial representation and a weighted Mean Squared Error (MSE) loss function to balance density distribution variations. Using this approach, my aim is to provide a practical and efficient biological data compression solution that can be used for educational and research purpose, while maintaining a reasonable compression ratio and reconstruction quality from file to file.
Cryogenic electron microscopy (Cryo-EM) has become an essential tool for capturing high-resolution biological structures. Despite its advantage in visualizations, the large storage size of Cryo-EM data file poses significant challenges for researchers and educators. This paper investigates the application of deep learning, specifically implicit neural representation (INR), to compress Cryo-EM biological data. The proposed approach first extracts the binary map of each file according to the density threshold. The density map is highly repetitive, ehich can be effectively compressed by GZIP. The neural network then trains to encode spatial density information, allowing the storage of network parameters and learnable latent vectors. To improve reconstruction accuracy, I further incorporate the positional encoding to enhance spatial representation and a weighted Mean Squared Error (MSE) loss function to balance density distribution variations. Using this approach, my aim is to provide a practical and efficient biological data compression solution that can be used for educational and research purpose, while maintaining a reasonable compression ratio and reconstruction quality from file to file.
AI Insights
- The project establishes Implicit Neural Representation (INR) as a promising framework for Cryo-EM data compression, balancing efficiency and fidelity. [3]
- The method achieves a compression ratio of approximately 10:1, reducing file sizes from 414 MB to around 40 MB, outperforming traditional GZIP compression. [3]
- Experimental results demonstrate notable progress in surpassing GZIP's compression ratio and achieving high reconstruction quality for structurally significant areas. [3]
- GZIP: a file format used for data compression that typically yields lower ratios on complex Cryo-EM data. [3]
- INR (Implicit Neural Representation): a framework for representing scenes or data using neural networks, allowing for efficient and accurate reconstruction. [3]
- Future work may focus on automating hyperparameter tuning and refining the INR architecture to reduce low-density errors. [3]
- Limitations persist in low-density regions, where mean errors exceed 1000% due to noise and sparsity. [3]
- The project establishes INR as a promising tool for Cryo-EM data management, particularly in resource-limited settings. [2]
- Cryo-EM (Cryogenic Electron Microscopy): a technique used to determine the three-dimensional structure of macromolecules, such as proteins. [1]
Why we are recommending this paper?
Due to your Interest in: Deep Learning
Due to your Interest in: Deep Learning
National Textile Universt
Abstract
This paper provides a review of deep learning applications in scene understanding in autonomous robots, including innovations in object detection, semantic and instance segmentation, depth estimation, 3D reconstruction, and visual SLAM. It emphasizes how these techniques address limitations of traditional geometric models, improve depth perception in real time despite occlusions and textureless surfaces, and enhance semantic reasoning to understand the environment better. When these perception modules are integrated into dynamic and unstructured environments, they become more effective in decisionmaking, navigation and interaction. Lastly, the review outlines the existing problems and research directions to advance learning-based scene understanding of autonomous robots.
This paper provides a review of deep learning applications in scene understanding in autonomous robots, including innovations in object detection, semantic and instance segmentation, depth estimation, 3D reconstruction, and visual SLAM. It emphasizes how these techniques address limitations of traditional geometric models, improve depth perception in real time despite occlusions and textureless surfaces, and enhance semantic reasoning to understand the environment better. When these perception modules are integrated into dynamic and unstructured environments, they become more effective in decisionmaking, navigation and interaction. Lastly, the review outlines the existing problems and research directions to advance learning-based scene understanding of autonomous robots.
Why we are recommending this paper?
Due to your Interest in: Deep Learning
Due to your Interest in: Deep Learning
University of Cambridge
Abstract
We consider the problem of ranking objects from noisy pairwise comparisons, for example, ranking tennis players from the outcomes of matches. We follow a standard approach to this problem and assume that each object has an unobserved strength and that the outcome of each comparison depends probabilistically on the strengths of the comparands. However, we do not assume to know a priori how skills affect outcomes. Instead, we present an efficient algorithm for simultaneously inferring both the unobserved strengths and the function that maps strengths to probabilities. Despite this problem being under-constrained, we present experimental evidence that the conclusions of our Bayesian approach are robust to different model specifications. We include several case studies to exemplify the method on real-world data sets.
We consider the problem of ranking objects from noisy pairwise comparisons, for example, ranking tennis players from the outcomes of matches. We follow a standard approach to this problem and assume that each object has an unobserved strength and that the outcome of each comparison depends probabilistically on the strengths of the comparands. However, we do not assume to know a priori how skills affect outcomes. Instead, we present an efficient algorithm for simultaneously inferring both the unobserved strengths and the function that maps strengths to probabilities. Despite this problem being under-constrained, we present experimental evidence that the conclusions of our Bayesian approach are robust to different model specifications. We include several case studies to exemplify the method on real-world data sets.
AI Insights
- The paper discusses various methods for analyzing paired comparison data, including the Bradley-Terry model, generalized linear mixed models, and Bayesian inference. [3]
- Paired comparison data: Data where each pair of items is compared to determine which one is preferred or superior. [3]
- Bradley-Terry model: A statistical model used to analyze paired comparison data, assuming that the probability of a item being preferred over another is proportional to its ability parameter. [3]
- The paper concludes by highlighting the importance of considering multiple methods and models when analyzing paired comparison data, as each method has its own strengths and limitations. [3]
- Some sections of the paper may be difficult to follow for readers without prior knowledge of paired comparison data analysis. [3]
- The authors discuss various applications of paired comparison data analysis, including sports, social networks, and animal behavior. [3]
- The paper discusses various statistical methods for analyzing paired comparison data, including the Bradley-Terry model, generalized linear mixed models, and Bayesian inference. [3]
- The authors also emphasize the need for further research in developing more robust and efficient methods for analyzing paired comparison data. [2]
Why we are recommending this paper?
Due to your Interest in: Ranking
Due to your Interest in: Ranking
TU Darmstadt
Abstract
The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games each are prominent open problems in their respective fields. While numerous natural candidates for efficient rules have been eliminated, all existing lower bound constructions are tailored to individual or small sets of pivot rules. We introduce a unified framework for formalizing classes of rules according to the information about the input that they rely on. Within this framework, we show lower bounds for \emph{ranking-based} classes of rules that base their decisions on orderings of the improving pivot steps induced by the underlying data. Our first result is a superpolynomial lower bound for strategy improvement, obtained via a family of sink parity games, which applies to memory-based generalizations of Bland's rule that only access the input by comparing the ranks of improving edges in some global order. Our second result is a subexponential lower bound for policy iteration, obtained via a family of Markov decision processes, which applies to memoryless rules that only access the input by comparing improving actions according to their ranks in a global order, their reduced costs, and the associated improvements in objective value. Both results carry over to the simplex method for linear programming.
The existence of a polynomial pivot rule for the simplex method for linear programming, policy iteration for Markov decision processes, and strategy improvement for parity games each are prominent open problems in their respective fields. While numerous natural candidates for efficient rules have been eliminated, all existing lower bound constructions are tailored to individual or small sets of pivot rules. We introduce a unified framework for formalizing classes of rules according to the information about the input that they rely on. Within this framework, we show lower bounds for \emph{ranking-based} classes of rules that base their decisions on orderings of the improving pivot steps induced by the underlying data. Our first result is a superpolynomial lower bound for strategy improvement, obtained via a family of sink parity games, which applies to memory-based generalizations of Bland's rule that only access the input by comparing the ranks of improving edges in some global order. Our second result is a subexponential lower bound for policy iteration, obtained via a family of Markov decision processes, which applies to memoryless rules that only access the input by comparing improving actions according to their ranks in a global order, their reduced costs, and the associated improvements in objective value. Both results carry over to the simplex method for linear programming.
Why we are recommending this paper?
Due to your Interest in: Ranking
Due to your Interest in: Ranking
Help us improve your experience!
This project is on its early stages your feedback can be pivotal on the future of the project.
Let us know what you think about this week's papers and suggestions!
Give Feedback